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: 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 (Breadth First Search Algorithm)

We can expand the search process/tree using BFS (Breadth First Search) Algorithm. We need also caching the node with location and balance so that same state nodes are not pushed to the queue. When we find a path, we simply return True, thus we can just use a hash set to store those failed paths aka Memoization.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution:
    def isThereAPath(self, grid: List[List[int]]) -> bool:
        rows = len(grid)
        cols = len(grid[0])
        
        if (rows + cols - 1) & 1:
            return False
                
        seen = set()
        q = deque([(0, 0, (-1, 1)[grid[0][0]])])
        while q:
            r, c, d = q.popleft()
            if r == rows - 1 and c == cols - 1:
                if d == 0:
                    return True
                continue
            if (r, c, d) in seen:
                continue
            seen.add((r, c, d))
            if r + 1 < rows:
                q.append((r + 1, c, d + (-1, 1)[grid[r + 1][c]]))
            if c + 1 < cols:
                q.append((r, c + 1, d + (-1, 1)[grid[r][c + 1]]))
        return False

class Solution:
    def isThereAPath(self, grid: List[List[int]]) -> bool:
        rows = len(grid)
        cols = len(grid[0])
        
        if (rows + cols - 1) & 1:
            return False
                
        seen = set()
        q = deque([(0, 0, (-1, 1)[grid[0][0]])])
        while q:
            r, c, d = q.popleft()
            if r == rows - 1 and c == cols - 1:
                if d == 0:
                    return True
                continue
            if (r, c, d) in seen:
                continue
            seen.add((r, c, d))
            if r + 1 < rows:
                q.append((r + 1, c, d + (-1, 1)[grid[r + 1][c]]))
            if c + 1 < cols:
                q.append((r, c + 1, d + (-1, 1)[grid[r][c + 1]]))
        return False

We can check for path/state duplication when we are about to en-queue or when we are polling the nodes from the queue aka de-queue. Usually, the former is better since the duplicate nodes are not pushed back to the queue in the first place.

We can have an early check to reject doing a full BFS algorithm when there is for sure non-existent path e.g. on a square maze where there are odd number of cells along the path which can’t be split into equal number of zeros and ones.

Time/space complexity is O(RCB) same as Depth First Search Algorithm.

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

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading…

845 words
Last Post: Teaching Kids Programming – Check if There is a Path With Equal Number of 0’s And 1’s (Maze, Recursion, Memoization, Dynamic Programming)
Next Post: Teaching Kids Programming – Minimum Number of Arrows to Burst Balloons (Greedy Algorithm)