LeetCode 2510. Check if There is a Path With Equal Number of 0's And 1's Solution in Java, C++, Python & Go | Explanation + Code

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

Solution 1: Memoization Search

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 × n × (m + n)). Here, m and n are the number of rows and columns of the matrix, respectively.

PythonJavaC++Go

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)(code-box)

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]; } }(code-box)

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); } };(code-box)

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) }(code-box)