Skip to content

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

Description

You are given a 0-indexed m x n binary matrix grid. You can move from a cell (row, col) to any of the cells (row + 1, col) or (row, col + 1).

Return true if there is a path from (0, 0) to (m - 1, n - 1) that visits an equal number of 0's and 1's. Otherwise return false.

 

Example 1:

Input: grid = [[0,1,0,0],[0,1,0,0],[1,0,1,0]]
Output: true
Explanation: The path colored in blue in the above diagram is a valid path because we have 3 cells with a value of 1 and 3 with a value of 0. Since there is a valid path, we return true.

Example 2:

Input: grid = [[1,1,0],[0,0,1],[1,0,0]]
Output: false
Explanation: There is no path in this grid with an equal number of 0's and 1's.

 

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 2 <= m, n <= 100
  • grid[i][j] is either 0 or 1.

Solutions

Thinking

Paths from the top-left to the bottom-right only move right or down, so their length is \(m+n-1\). An odd length cannot split equally between \(0\)s and \(1\)s. Full path enumeration is too large for \(m,n\le 100\).

The target is \(s=(m+n-1)/2\) ones (and the same number of zeros). State \((i,j,k)\) is position \((i,j)\) with \(k\) ones so far; prune when \(k\) or the zero count already exceeds \(s\). Memoization yields \(O(mn(m+n))\) states.

According to the problem description, we know that the number of 0s and 1s on the path from the top-left corner to the bottom-right corner is equal, and the total number is \(m + n - 1\), which means the number of 0s and 1s are both \((m + n - 1) / 2\).

Therefore, we can use memoization search, starting from the top-left corner and moving right or down until reaching the bottom-right corner, to check if the number of 0s and 1s on the path is equal.

The time complexity is \(O(m \times n \times (m + n))\). Here, \(m\) and \(n\) are the number of rows and columns of the matrix, respectively.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def isThereAPath(self, grid: List[List[int]]) -> bool:
        @cache
        def dfs(i, j, k):
            if i >= m or j >= n:
                return False
            k += grid[i][j]
            if k > s or i + j + 1 - k > s:
                return False
            if i == m - 1 and j == n - 1:
                return k == s
            return dfs(i + 1, j, k) or dfs(i, j + 1, k)

        m, n = len(grid), len(grid[0])
        s = m + n - 1
        if s & 1:
            return False
        s >>= 1
        return dfs(0, 0, 0)

 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
36
37
38
class Solution {
    private int s;
    private int m;
    private int n;
    private int[][] grid;
    private Boolean[][][] f;

    public boolean isThereAPath(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        this.grid = grid;
        s = m + n - 1;
        f = new Boolean[m][n][s];
        if (s % 2 == 1) {
            return false;
        }
        s >>= 1;
        return dfs(0, 0, 0);
    }

    private boolean dfs(int i, int j, int k) {
        if (i >= m || j >= n) {
            return false;
        }
        k += grid[i][j];
        if (f[i][j][k] != null) {
            return f[i][j][k];
        }
        if (k > s || i + j + 1 - k > s) {
            return false;
        }
        if (i == m - 1 && j == n - 1) {
            return k == s;
        }
        f[i][j][k] = dfs(i + 1, j, k) || dfs(i, j + 1, k);
        return f[i][j][k];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool isThereAPath(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int s = m + n - 1;
        if (s & 1) return false;
        int f[m][n][s];
        s >>= 1;
        memset(f, -1, sizeof f);
        function<bool(int, int, int)> dfs = [&](int i, int j, int k) -> bool {
            if (i >= m || j >= n) return false;
            k += grid[i][j];
            if (f[i][j][k] != -1) return f[i][j][k];
            if (k > s || i + j + 1 - k > s) return false;
            if (i == m - 1 && j == n - 1) return k == s;
            f[i][j][k] = dfs(i + 1, j, k) || dfs(i, j + 1, k);
            return f[i][j][k];
        };
        return dfs(0, 0, 0);
    }
};

 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
func isThereAPath(grid [][]int) bool {
    m, n := len(grid), len(grid[0])
    s := m + n - 1
    if s%2 == 1 {
        return false
    }
    s >>= 1
    f := [100][100][200]int{}
    var dfs func(i, j, k int) bool
    dfs = func(i, j, k int) bool {
        if i >= m || j >= n {
            return false
        }
        k += grid[i][j]
        if f[i][j][k] != 0 {
            return f[i][j][k] == 1
        }
        f[i][j][k] = 2
        if k > s || i+j+1-k > s {
            return false
        }
        if i == m-1 && j == n-1 {
            return k == s
        }
        res := dfs(i+1, j, k) || dfs(i, j+1, k)
        if res {
            f[i][j][k] = 1
        }
        return res
    }
    return dfs(0, 0, 0)
}

Comments