Problem Description

You have a 2D binary grid (containing only 0s and 1s) with m rows and n columns. Starting from the top-left corner at position (0, 0), you need to reach the bottom-right corner at position (m-1, n-1).

From any cell (row, col), you can only move in two directions:

• Down: to cell (row + 1, col)
• Right: to cell (row, col + 1)

Your task is to determine if there exists a path from (0, 0) to (m-1, n-1) where you visit an equal number of 0s and 1s along the way.

Return true if such a path exists, otherwise return false.

For example, if you have a 3×3 grid and your path visits cells containing values [1, 0, 1, 1, 0], you've visited three 1s and two 0s, which are not equal, so this wouldn't be a valid path. You need to find if any possible path from start to end has exactly the same count of 0s and 1s.

Intuition

The key insight is that any path from (0, 0) to (m-1, n-1) will have exactly m + n - 1 cells visited (including start and end positions). This is because we need to make m-1 down moves and n-1 right moves to reach the destination.

For the path to have an equal number of 0s and 1s, we need (m + n - 1) / 2 zeros and (m + n - 1) / 2 ones. This immediately tells us that if m + n - 1 is odd, it's impossible to have equal counts, so we can return false right away.

When m + n - 1 is even, we need to track how many 1s we've collected along our path. We can use dynamic programming with memoization to explore all possible paths. The state we need to track is:

• Current position (i, j)
• Number of 1s collected so far k

We can prune our search early using two observations:

1. If we've already collected more 1s than the target count s = (m + n - 1) / 2, we can stop exploring this path
2. If the remaining cells aren't enough to collect the required number of 0s, we can also stop. The number of 0s collected so far is (i + j + 1 - k), and if this exceeds our target s, we know this path won't work

At the destination (m-1, n-1), we check if we've collected exactly s ones (which means we also collected exactly s zeros), making the counts equal.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution uses memoization search (dynamic programming with recursion and caching) to explore all possible paths from the top-left to bottom-right corner.

First, we check if a valid path is even possible:

• Calculate the total path length: s = m + n - 1
• If s is odd (checked using s & 1), return false immediately since we can't split an odd number equally
• If even, set s = s / 2 (using s >>= 1 for efficiency) as our target count for both 0s and 1s

The main algorithm uses a DFS function dfs(i, j, k) where:

• i, j represents the current position in the grid
• k tracks the number of 1s collected so far

For each recursive call:

1. Boundary check: If we go out of bounds (i >= m or j >= n), return false

2. Update count: Add the current cell's value to our 1s count: k += grid[i][j]

3. Pruning conditions:

   • If k > s: We've collected too many 1s, impossible to balance
   • If i + j + 1 - k > s: We've collected too many 0s (since zeros collected = cells visited - ones collected), impossible to balance

4. Base case: If we reach the destination (i == m-1 and j == n-1), check if k == s (exactly half 1s means exactly half 0s too)

5. Recursive exploration: Try both possible moves:

   • Move down: dfs(i + 1, j, k)
   • Move right: dfs(i, j + 1, k)
   • Return true if either path succeeds

The @cache decorator memoizes the results, preventing redundant calculations for the same state (i, j, k), which significantly improves performance from exponential to polynomial time complexity.

The algorithm starts with dfs(0, 0, 0) from the top-left corner with zero 1s collected initially.

Example Walkthrough

Let's walk through a small example with a 3×3 grid:

Grid:
[1, 0, 1]
[0, 1, 0]  
[1, 0, 1]

Step 1: Check if equal counts are possible

• Path length = m + n - 1 = 3 + 3 - 1 = 5 cells
• Since 5 is odd, we cannot have equal 0s and 1s (can't split 5 equally)
• Return false immediately

Let's try another example with a 2×3 grid:

Grid:
[1, 0, 1]
[0, 1, 1]

Step 1: Check path length

• Path length = 2 + 3 - 1 = 4 cells
• Since 4 is even, we can potentially have 2 ones and 2 zeros
• Target count s = 4 / 2 = 2

Step 2: Start DFS from (0,0)

• Call dfs(0, 0, 0) - starting at top-left with 0 ones collected

Step 3: Process cell (0,0)

• Current cell value = 1, so k = 0 + 1 = 1
• Check pruning: k=1 ≤ s=2 ✓ and zeros=1 ≤ s=2 ✓
• Not at destination, explore both moves

Step 4: Explore from (0,0)

Path 1: Go right to (0,1)

• dfs(0, 1, 1) - carrying 1 one
• Cell value = 0, so k stays 1
• Cells visited = 2, zeros = 2-1 = 1 ≤ 2 ✓
• From (0,1), can go right to (0,2) or down to (1,1)

Path 1a: (0,0)→(0,1)→(0,2)→(1,2)

• At (0,2): k = 1+1 = 2, zeros = 1
• At (1,2): k = 2+1 = 3, zeros = 1
• k > s, prune this path ✗

Path 1b: (0,0)→(0,1)→(1,1)→(1,2)

• At (1,1): k = 1+1 = 2, zeros = 1
• At (1,2): k = 2+1 = 3, zeros = 1
• k > s, prune this path ✗

Path 2: Go down to (1,0)

• dfs(1, 0, 1) - carrying 1 one
• Cell value = 0, so k stays 1
• From (1,0), must go right (only option to reach destination)

Path 2a: (0,0)→(1,0)→(1,1)→(1,2)

• At (1,1): k = 1+1 = 2, zeros = 2
• At (1,2): k = 2+1 = 3, zeros = 2
• k > s, prune this path ✗

Step 5: Check all paths All paths result in either:

• 3 ones and 1 zero (paths through multiple 1s)
• 2 ones and 2 zeros (if we could find such a path)

Let's trace one valid scenario with a modified grid:

Grid:
[1, 0, 0]
[0, 1, 1]

Path: (0,0)→(0,1)→(0,2)→(1,2)

• Values visited: [1, 0, 0, 1]
• Count: 2 ones, 2 zeros ✓
• This would return true

The memoization ensures that if we encounter the same state (i, j, k) again, we reuse the cached result instead of recalculating, making the algorithm efficient.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × n × (m + n))

The time complexity is determined by the memoized DFS function. The @cache decorator ensures each unique state (i, j, k) is computed only once.

• i can take values from 0 to m-1 (m possible values)
• j can take values from 0 to n-1 (n possible values)
• k represents the count of 1s encountered so far. In the worst case, k can range from 0 to min(i+j, m+n-1). Since we're traversing from (0,0) to (m-1,n-1), the maximum value of k is bounded by the total path length m+n-1

Therefore, the total number of unique states is O(m × n × (m + n)).

Space Complexity: O(m × n × (m + n))

The space complexity consists of:

• Memoization cache: The @cache decorator stores all computed states (i, j, k), which requires O(m × n × (m + n)) space
• Recursion stack: In the worst case, the recursion depth can go up to m + n - 1 (the length of the path from top-left to bottom-right), contributing O(m + n) to space complexity

The dominant factor is the memoization cache, giving us an overall space complexity of O(m × n × (m + n)).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Path Length Calculation

A common mistake is forgetting that the path length is m + n - 1, not m + n. When moving from (0,0) to (m-1, n-1), we make exactly m-1 down moves and n-1 right moves, visiting a total of (m-1) + (n-1) + 1 = m + n - 1 cells.

Wrong approach:

path_length = rows + cols  # Incorrect!

Correct approach:

path_length = rows + cols - 1  # Correct

2. Forgetting to Include Starting Cell Value

Some implementations forget to count the value at the starting position (0,0) in their initial call. The grid value at the starting position must be included in the count.

Wrong approach:

# Starting without considering grid[0][0]
return dfs(0, 0, 0)  # This is actually correct, but only because
                     # we add grid[row][col] inside dfs

Alternative correct approach if counting outside:

# If you count before entering the cell
return dfs(0, 0, grid[0][0])

3. Inefficient Pruning or No Pruning

Without proper pruning conditions, the algorithm explores many unnecessary paths. The key insight is that if we've already collected too many 1s or 0s to possibly balance them by the destination, we should stop exploring that path.

Inefficient approach:

def dfs(row, col, ones_count):
    if row >= rows or col >= cols:
        return False
  
    ones_count += grid[row][col]
  
    # No pruning - explores all paths even when impossible
    if row == rows - 1 and col == cols - 1:
        return ones_count == target_ones
  
    return dfs(row + 1, col, ones_count) or dfs(row, col + 1, ones_count)

Optimized approach with pruning:

def dfs(row, col, ones_count):
    if row >= rows or col >= cols:
        return False
  
    ones_count += grid[row][col]
  
    # Pruning conditions
    zeros_count = row + col + 1 - ones_count
    if ones_count > target_ones or zeros_count > target_ones:
        return False  # Early termination
  
    if row == rows - 1 and col == cols - 1:
        return ones_count == target_ones
  
    return dfs(row + 1, col, ones_count) or dfs(row, col + 1, ones_count)

4. Missing Memoization Leading to Time Limit Exceeded

Without memoization, the same states (row, col, ones_count) are computed multiple times, leading to exponential time complexity.

Wrong approach:

# No @cache decorator or manual memoization
def dfs(row, col, ones_count):
    # ... rest of the code

Correct approach:

@cache  # Critical for performance!
def dfs(row, col, ones_count):
    # ... rest of the code

5. Integer Division vs Floor Division

When calculating the target count, using regular division / instead of integer division // or bit shifting can cause issues.

Potentially problematic:

target_ones = path_length / 2  # Returns float in Python 3

Correct approaches:

target_ones = path_length // 2  # Integer division
# OR
target_ones = path_length >> 1  # Bit shift (more efficient)