Skip to content

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

Approach 1: 3D DP

  • Time: $O(mn(m + n))$
  • Space: $O(mn(m + n))$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
 public:
  bool isThereAPath(vector<vector<int>>& grid) {
    m = grid.size();
    n = grid[0].size();
    // Map negative (# of 0s - # of 1s) to non-negative one.
    cells = m + n - 1;
    if (cells & 1)
      return false;
    dp.resize(m, vector<vector<int>>(n, vector<int>(cells * 2 + 1, -1)));
    return isThereAPath(grid, 0, 0, 0);
  }

 private:
  int m;
  int n;
  int cells;
  // dp[i][j][cells + k] := 1 if there's a path to grid[i][j] s.t.
  // k = (# of 0s - # of 1s).
  vector<vector<vector<int>>> dp;

  bool isThereAPath(const vector<vector<int>>& grid, int i, int j, int sum) {
    if (i == m || j == n)
      return false;
    sum += grid[i][j] == 0 ? 1 : -1;
    if (i == m - 1 && j == n - 1)
      return sum == 0;
    int& ans = dp[i][j][cells + sum];
    if (ans != -1)
      return ans == 1 ? true : false;
    ans =
        isThereAPath(grid, i + 1, j, sum) || isThereAPath(grid, i, j + 1, sum);
    return ans == 1 ? true : false;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
  public boolean isThereAPath(int[][] grid) {
    m = grid.length;
    n = grid[0].length;
    // Map negative (# of 0s - # of 1s) to non-negative one.
    cells = m + n - 1;
    if (cells % 2 == 1)
      return false;
    dp = new Boolean[m][n][cells * 2 + 1];
    return isThereAPath(grid, 0, 0, 0);
  }

  private int m;
  private int n;
  private int cells;
  // dp[i][j][cells + k] := 1 if there's a path to grid[i][j] s.t.
  // k = (# of 0s - # of 1s).
  private Boolean[][][] dp;

  private boolean isThereAPath(int[][] grid, int i, int j, int sum) {
    if (i == m || j == n)
      return false;
    sum += grid[i][j] == 0 ? 1 : -1;
    if (i == m - 1 && j == n - 1)
      return sum == 0;
    if (dp[i][j][cells + sum] != null)
      return dp[i][j][cells + sum];
    return dp[i][j][cells + sum] =
               isThereAPath(grid, i + 1, j, sum) || isThereAPath(grid, i, j + 1, sum);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
  def isThereAPath(self, grid: List[List[int]]) -> bool:
    m = len(grid)
    n = len(grid[0])
    if m + n - 1 & 1:
      return False

    @functools.lru_cache(None)
    def dp(i: int, j: int, summ: int) -> bool:
      if i == m or j == n:
        return False
      summ += 1 if grid[i][j] == 0 else -1
      if i == m - 1 and j == n - 1:
        return summ == 0
      return dp(i + 1, j, summ) or dp(i, j + 1, summ)

    return dp(0, 0, 0)

Approach 2: 2D DP

  • Time: $O(mn)$
  • Space: $O(mn)$