Check if There is a Path With Equal Number of 0's And 1's

Check if There is a Path With Equal Number of 0's And 1's

What is this problem about?

In this coding problem, you are given an $m imes n$ binary matrix. You start at the top-left corner $(0, 0)$ and want to reach the bottom-right corner $(m-1, n-1)$. You can only move down or right. A path is valid if the number of 0s is exactly equal to the number of 1s in that path.

Why is this asked in interviews?

Google asks this to test your proficiency with Dynamic Programming and Matrix traversal. It’s a variation of the "unique paths" problem but with an added constraint. It evaluates whether you can identify the necessary state to track (the "balance" of 0s and 1s) and whether you can optimize that state using properties of the grid (like the fixed path length).

Algorithmic pattern used

This is a Dynamic Programming (DP) on a Matrix problem. The path length from $(0, 0)$ to $(m-1, n-1)$ is always $m + n - 1$. For the number of 0s to equal the number of 1s, this total length must be even (which means $m+n$ must be odd). The DP state dp[i][j] could store a set of possible "balances" (number of 1s minus number of 0s) that can be reached at cell $(i, j)$. If 0 is in the set at the bottom-right cell, a valid path exists.

Example explanation

Matrix $2 imes 3$: 1 1 0 0 0 1 Path length: $2+3-1 = 4$.

1. Path 1: (0,0) -> (0,1) -> (0,2) -> (1,2). Values: [1, 1, 0, 1]. Count: 3 ones, 1 zero. (Invalid)
2. Path 2: (0,0) -> (1,0) -> (1,1) -> (1,2). Values: [1, 0, 0, 1]. Count: 2 ones, 2 zeros. (Valid!) Result: True.

Common mistakes candidates make

A common error is not realizing that the total path length must be even for an equal count to be possible. Another is using a simple boolean DP that only tracks the best balance, which is incorrect because a "lesser" balance might be the only one that can be corrected later. Using a bitset to store possible balances is a common optimization for this problem.

Interview preparation tip

When a grid problem involves a "sum" or "count" constraint, think about what values are possible at each cell. If the range of values is small, you can store all possible outcomes in a set or a bitmask at each DP state.