Teaching Kids Programming – Check if There is a Path With Equal Number of 0’s And 1’s (Maze, Recursion, Memoization, Dynamic Programming)

Teaching Kids Programming: Videos on Data Structures and Algorithms

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.

Check if There is a Path With Equal Number of 0’s And 1’s

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.

Hints:
Can you use dynamic programming to solve the problem?
Let dp[i][j][diff] be true if there is a path from the cell (i, j) to (m – 1, n – 1) such that the difference between the number of 0’s and the number of 1’s that we visited so far is diff, or false otherwise. The answer to the problem will be dp[0][0][0]. How do you compute this dp?

Check if There is a Path With Equal Number of 0’s And 1’s (Maze/Recursion/Top Down Dynamic Programming)

Suppose there are R rows and C columns of the given Maze, and we can learn that it takes R+C-2 steps to reach to bottom right corner from the top left corner. The path contains R+C-1 numbers, and if this is odd, we can’t find any path that contains equal numbers of zeros and ones.

We can bruteforce all the path via Recursion. And we can make it Top Down Dynamic Programming by adding a @cache keyword to memoize the state of (R, C, B) where R, C is the location coordinate and B is the balance when we meet one “1” we increment the balance, otherwise we decrement the balance.

At each Recursive call dfs(r, c, b) we have two states to solve, which are the two directions. And of course, it the next move crosses the bounary, we simply ignore it.

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:
        rows = len(grid)
        cols = len(grid[0])
        
        if (rows + cols - 1) & 1:
            return False
        
        @cache
        def dfs(i, j, d):
            # d += 1 if grid[i][j] == 1 else -1
            d += (-1, 1)[grid[i][j]]
            if i == rows - 1 and j == cols - 1:
                return d == 0
            if i + 1 < rows and dfs(i + 1, j, d):
                return True
            if j + 1 < cols and dfs(i, j + 1, d):
                return True
            return False
        
        return dfs(0, 0, 0)

class Solution:
    def isThereAPath(self, grid: List[List[int]]) -> bool:
        rows = len(grid)
        cols = len(grid[0])
        
        if (rows + cols - 1) & 1:
            return False
        
        @cache
        def dfs(i, j, d):
            # d += 1 if grid[i][j] == 1 else -1
            d += (-1, 1)[grid[i][j]]
            if i == rows - 1 and j == cols - 1:
                return d == 0
            if i + 1 < rows and dfs(i + 1, j, d):
                return True
            if j + 1 < cols and dfs(i, j + 1, d):
                return True
            return False
        
        return dfs(0, 0, 0)

We can also traverse backwards from the bottom-right (destination) back to the source (top-left corner).

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:
        rows = len(grid)
        cols = len(grid[0])
        
        if (rows + cols - 1) & 1:
            return False
        
        @cache
        def dfs(i, j, d):
            # d += 1 if grid[i][j] == 1 else -1
            d += (-1, 1)[grid[i][j]]
            if i == 0 and j == 0:
                return d == 0
            if i > 0 and dfs(i - 1, j, d):
                return True
            if j > 0 and dfs(i, j - 1, d):
                return True
            return False
        
        return dfs(rows - 1, cols - 1, 0)

class Solution:
    def isThereAPath(self, grid: List[List[int]]) -> bool:
        rows = len(grid)
        cols = len(grid[0])
        
        if (rows + cols - 1) & 1:
            return False
        
        @cache
        def dfs(i, j, d):
            # d += 1 if grid[i][j] == 1 else -1
            d += (-1, 1)[grid[i][j]]
            if i == 0 and j == 0:
                return d == 0
            if i > 0 and dfs(i - 1, j, d):
                return True
            if j > 0 and dfs(i, j - 1, d):
                return True
            return False
        
        return dfs(rows - 1, cols - 1, 0)

The time/space complexity is O(RCB) as this is the upper bound of the number of the states to compute.

Check if There is a Path With Equal Number of 0’s And 1’s

• Teaching Kids Programming – Check if There is a Path With Equal Number of 0’s And 1’s (Breadth First Search Algorithm)
• Teaching Kids Programming – Check if There is a Path With Equal Number of 0’s And 1’s (Maze, Recursion, Memoization, Dynamic Programming)

–EOF (The Ultimate Computing & Technology Blog) —