Check if There is a Path With Equal Number of 0's And 1's - Solution & Explanation

Problem Overview: You start at the top-left cell of a binary matrix and can only move right or down. The goal is to reach the bottom-right cell using a path that contains the same number of 0s and 1s. The path length is fixed at m + n - 1, so a valid path must have exactly half zeros and half ones.

A quick observation simplifies the problem: if m + n - 1 is odd, the path length cannot be split evenly between zeros and ones. In that case, the answer is immediately false.

Approach 1: Brute Force DFS (Exponential Time)

Enumerate every possible path from (0,0) to (m-1,n-1) using depth‑first search. At each step, move either right or down while tracking how many zeros and ones you have seen so far. When the path reaches the bottom-right cell, check whether the counts are equal.

This approach explores the full decision tree of paths, which is roughly O(2^(m+n)) in the worst case. Space complexity is O(m+n) for the recursion stack. It works for very small grids but quickly becomes infeasible as the grid grows.

Approach 2: DFS with Memoization (Dynamic Programming) (Time: O(m * n * (m+n)), Space: O(m * n * (m+n)))

The key insight: different paths can reach the same cell with the same difference between the number of ones and zeros. Once you know that state leads to failure, you never need to recompute it.

Convert the problem into a running balance: treat 1 as +1 and 0 as -1. A valid path ends with total sum 0. During DFS, track the current cell (r, c) and the running sum. Use memoization to store states (r, c, balance) that have already been explored.

Pruning improves performance further. From a given position, you know how many steps remain before reaching the end. If the remaining steps cannot compensate for the current balance, the path cannot reach zero. That branch can be cut early.

This transforms the brute-force search into a dynamic programming problem over a matrix, caching repeated states. The algorithm visits each cell with a limited range of balances, resulting in roughly O(m * n * (m+n)) time and the same order of memory.

The technique combines DFS state exploration with memoization, a classic pattern in dynamic programming problems that operate on grids or paths.

Recommended for interviews: DFS with memoization is the expected solution. Brute force shows you understand the path search space, but memoization demonstrates the ability to identify overlapping subproblems and apply array and grid DP optimization. Interviewers usually expect the parity check plus memoized search with pruning.