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

📝 Problem Details

• Title: 2510. Check if There is a Path With Equal Number of 0's and 1's
• Link: https://leetcode.com/problems/check-if-there-is-a-path-with-equal-number-of-0s-and-1s/
• Difficulty: Medium
• Tags/Categories: {{tags/categories}}

input binary matrix grid you can move down or right return true if there is a path from 0,0 to m-1, n-1 that visits an equal number of 0s and 1s

💭What Were My Initial Thoughts?

brute force approach:
- DFS from the top left to bottom right cell, keeping track of the number of 0s and 1s in the path

to optimize:
- let dp[i][j][balance] be true if there's a path from (0,0) to (i,j) that results in a difference of balance between the count of 1s and 0s 
	- balance = count1s - count0s
- we return true if dp[m-1][n-1][0] is true (equal number of 0s and 1s)

💡 Explanation of Solution

• First, we check a quick edge case: if (m + n - 1) is odd, we cannot split the path evenly into 0s and 1s — return false early.
• We define a 3D DP state:
  • dp[i][j][balance] = true if it’s possible to reach (i, j) from (0, 0) with a balance of balance.
  • To prevent negative indices, we offset balance by a constant (e.g., offset = m + n), so balance ranges from -offset to +offset.
• Starting from (0, 0), we initialize the base case using the value of grid[0][0].
• At each step, we transition from (i-1, j) or (i, j-1) and update balance accordingly.
• Finally, return whether dp[m-1][n-1][offset] is true (i.e., balance 0).

⌛ Complexity Analysis

Time Complexity: O(m * n * (m + n))
- For each cell (i, j), balance ranges from -maxLen to +maxLen → 2 * (m + n)
- We explore each possible state once.

Space Complexity: O(m * n * (m + n))
- We store DP states for each (i, j, balance) triple.

Brute Force Solution (TLE)

class Solution {
public:
    bool dfs(vector<vector<int>>& grid, int i, int j, int count0, int count1) {
        int m = grid.size();
        int n = grid[0].size();
 
        // Count current cell
        if (grid[i][j] == 0) count0++;
        else count1++;
 
        // If we reach bottom-right cell, check if 0s == 1s
        if (i == m - 1 && j == n - 1) {
            return count0 == count1;
        }
 
        bool result = false;
 
        // Move down
        if (i + 1 < m) {
            result |= dfs(grid, i + 1, j, count0, count1);
        }
 
        // Move right
        if (j + 1 < n) {
            result |= dfs(grid, i, j + 1, count0, count1);
        }
 
        return result;
    }
 
    bool isThereAPath(vector<vector<int>>& grid) {
        int totalSteps = grid.size() + grid[0].size() - 1;
 
        // If the path length is odd, equal 0s and 1s is impossible
        if (totalSteps % 2 != 0) return false;
 
        return dfs(grid, 0, 0, 0, 0);
    }
};

💻 Optimized DP Solution

class Solution {
public:
    bool isThereAPath(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int maxLen = m + n; // max possible path length
        int offset = maxLen; // offset for negative balance indexing
 
        // Early return if total steps is odd
        if ((m + n - 1) % 2 != 0) return false;
 
        // 3D DP array: dp[i][j][balance]
        vector<vector<unordered_set<int>>> dp(m, vector<unordered_set<int>>(n));
 
        // Initialize start position
        int start = grid[0][0] == 1 ? 1 : -1;
        dp[0][0].insert(start);
 
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i == 0 && j == 0) continue;
                int curr = grid[i][j] == 1 ? 1 : -1;
                if (i > 0) {
                    for (int b : dp[i - 1][j]) {
                        dp[i][j].insert(b + curr);
                    }
                }
                if (j > 0) {
                    for (int b : dp[i][j - 1]) {
                        dp[i][j].insert(b + curr);
                    }
                }
            }
        }
 
        return dp[m - 1][n - 1].count(0);
    }
};