Skip to content

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

  • 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
class Solution {
 public:
  bool isThereAPath(vector<vector<int>>& grid) {
    const int m = grid.size();
    const int n = grid[0].size();
    // Map negative (the number of 0s - the number of 1s) to non-negative one.
    const int cells = m + n - 1;
    if (cells % 2 == 1)
      return false;
    vector<vector<vector<int>>> mem(
        m, vector<vector<int>>(n, vector<int>(cells * 2 + 1, -1)));
    return isThereAPath(grid, 0, 0, 0, cells, mem);
  }

 private:
  // Returns 1 if there's a path to grid[i][j]
  // s.t. `sum` = (the number of 0s - the number of 1s).
  bool isThereAPath(const vector<vector<int>>& grid, int i, int j, int sum,
                    const int& cells, vector<vector<vector<int>>>& mem) {
    if (i == grid.size() || j == grid[0].size())
      return false;
    sum += grid[i][j] == 0 ? 1 : -1;
    if (i == grid.size() - 1 && j == grid[0].size() - 1)
      return sum == 0;
    const int k = cells + sum;
    if (mem[i][j][k] != -1)
      return mem[i][j][k];
    return mem[i][j][k] = isThereAPath(grid, i + 1, j, sum, cells, mem) ||
                          isThereAPath(grid, i, j + 1, sum, cells, mem);
  }
};

 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
class Solution {
  public boolean isThereAPath(int[][] grid) {
    final int m = grid.length;
    final int n = grid[0].length;
    // Map negative (the number of 0s - the number of 1s) to non-negative one.
    final int cells = m + n - 1;
    if (cells % 2 == 1)
      return false;
    Boolean[][][] mem = new Boolean[m][n][cells * 2 + 1];
    return isThereAPath(grid, 0, 0, 0, cells, mem);
  }

  // Returns 1 if there's a path to grid[i][j]
  // s.t. `sum` = (the number of 0s - the number of 1s).
  private boolean isThereAPath(int[][] grid, int i, int j, int sum, final int cells,
                               Boolean[][][] mem) {
    if (i == grid.length || j == grid[0].length)
      return false;
    sum += grid[i][j] == 0 ? 1 : -1;
    if (i == grid.length - 1 && j == grid[0].length - 1)
      return sum == 0;
    final int k = cells + sum;
    if (mem[i][j][k] != null)
      return mem[i][j][k];
    return mem[i][j][k] = isThereAPath(grid, i + 1, j, sum, cells, mem) ||
                          isThereAPath(grid, i, j + 1, sum, cells, mem);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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:
      """
      Returns 1 if there's a path to grid[i][j] s.t.
      `summ` = (the number of 0s - the number of 1s).
      """
      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)