We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

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

Number: 2653

Difficulty: Medium

Paid? Yes

Companies: Google

Problem Description

Given an m x n binary matrix, determine if there exists a valid path from the top-left cell (0, 0) to the bottom-right cell (m - 1, n - 1) that only moves either down or right and visits an equal number of 0's and 1's. A valid path must satisfy that the total number of cells visited (which is m+n-1) contains half 0’s and half 1’s.

Key Insights

  • The only possible moves are down and right.
  • The length of any valid path is fixed to m+n-1. For a path to have an equal number of 0's and 1's, m+n-1 must be even.
  • Use DFS (or DP) with memoization to explore all possible paths while tracking the difference between the count of zeros and ones.
  • The state is defined by the current position (row, col) and the difference (count0 - count1) so far.
  • A valid end state is reached when (row, col) is the bottom-right cell and the difference is zero.

Space and Time Complexity

Time Complexity: O(m * n * D) where D is the range of possible differences (bounded by the path length, roughly m+n).
Space Complexity: O(m * n * D) for the recursion stack and memoization.

Solution

We use a recursive DFS approach with memoization to keep track of states we have already processed. Each state is represented by (row, col, currentDifference) where currentDifference is the difference between the number of 0's and 1's encountered so far (with 0 incrementing the difference and 1 decrementing it). We start from the top-left corner and at every step move either right or down. When reaching the bottom-right cell, we check if the difference is zero.

Before starting, a quick check on the parity of (m+n-1) can quickly rule out the possibility of a valid path if it is odd.

Code Solutions

def hasEqualPath(grid):
    m, n = len(grid), len(grid[0])
    # If total number of cells in the path is odd, it's impossible to split evenly.
    if (m + n - 1) % 2 != 0:
        return False

    # Use memo to avoid reprocessing the same state: (row, col, diff)
    memo = {}

    # Helper DFS function: r, c - current cell indices; diff - current (count0 - count1)
    def dfs(r, c, diff):
        # If out of bounds, return False
        if r >= m or c >= n:
            return False
        # Update the difference based on current cell value
        # If grid[r][c] is 0, diff increases; if 1, diff decreases.
        currDiff = diff + (1 if grid[r][c] == 0 else -1)
        # If reached bottom-right, check if diff becomes exactly zero.
        if r == m - 1 and c == n - 1:
            return currDiff == 0
        # If the state was already computed, return result.
        if (r, c, currDiff) in memo:
            return memo[(r, c, currDiff)]

        # Explore the next moves: down and right.
        res = dfs(r + 1, c, currDiff) or dfs(r, c + 1, currDiff)
        memo[(r, c, currDiff)] = res
        return res

    # Start DFS from (0, 0) with initial difference 0.
    return dfs(0, 0, 0)

# Example usage:
grid_example = [[0,1,0,0],[0,1,0,0],[1,0,1,0]]
print(hasEqualPath(grid_example))  # Expected output: True
← Back to All Questions