Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2510.html

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

  • 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];
        }
    }
    
  • 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);
        }
    };
    
  • 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)
    
    
  • 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)
    }
    

All Problems

All Solutions