Shortest Path in Binary Matrix

▶

Steps

setup

Check start and end cells for blockage

The algorithm checks if the start cell (0,0) or the end cell (1,1) is blocked. Since both are open (0), the algorithm proceeds.

💡 If either start or end is blocked, no path exists, so this early check saves unnecessary work.

Line:

if grid[0][0] != 0 or grid[n-1][n-1] != 0:
    return -1

💡 The path can only exist if both ends are accessible.

setup

Initialize queues and visited sets

Initialize start_queue with (0,0) and end_queue with (1,1). Mark both as visited with distance 1.

💡 Queues hold nodes to explore next; visited sets track distances and prevent revisiting.

Line:

start_queue = deque([(0, 0)])
end_queue = deque([(n-1, n-1)])
start_visited = {(0, 0): 1}
end_visited = {(n-1, n-1): 1}

💡 Bidirectional BFS starts from both ends simultaneously to reduce search space.

traverse

Start BFS from start side: dequeue (0,0)

Dequeue node (0,0) from start_queue to explore its neighbors.

💡 Processing nodes in queue order ensures shortest path discovery.

Line:

r, c = queue.popleft()  # (0,0) from start_queue

💡 We explore neighbors of (0,0) to find new reachable nodes.

compare

Explore neighbor (0,1) of (0,0)

Check neighbor (0,1). It is blocked (value 1), so it is skipped.

💡 Blocked cells cannot be part of the path, so we ignore them.

Line:

if grid[nr][nc] == 0:  # (0,1) is 1, blocked

💡 Only open cells (0) can be added to the search frontier.

compare

Explore neighbor (1,0) of (0,0)

Check neighbor (1,0). It is blocked (value 1), so it is skipped.

💡 Blocked cells are ignored to avoid invalid paths.

Line:

if grid[nr][nc] == 0:  # (1,0) is 1, blocked

💡 Blocked neighbors do not expand the search.

compare

Explore neighbor (1,1) of (0,0)

Check neighbor (1,1). It is open and in the end_visited set, so the searches meet here.

💡 Finding a node in both visited sets means the shortest path is found.

Line:

if (nr, nc) in other_visited:
    return visited[(r, c)] + other_visited[(nr, nc)]

💡 The shortest path length is the sum of distances from both ends to the meeting node.

traverse

Start BFS from end side: dequeue (1,1)

Dequeue node (1,1) from end_queue to explore its neighbors.

💡 Processing nodes from the end side helps meet the start side search in the middle.

Line:

r, c = queue.popleft()  # (1,1) from end_queue

💡 Exploring neighbors of (1,1) could find a meeting point if not already found.

compare

Explore neighbor (0,0) of (1,1)

Check neighbor (0,0). It is open and already visited by start side, so the searches meet here.

💡 Finding a node in both visited sets confirms the shortest path.

Line:

if (nr, nc) in other_visited:
    return visited[(r, c)] + other_visited[(nr, nc)]

💡 The shortest path length is confirmed by meeting node visited from both sides.

reconstruct

Return shortest path length

The algorithm returns 2 as the shortest path length from (0,0) to (1,1).

💡 The sum of distances from both ends to the meeting node gives the shortest path length.

Line:

return visited[(r, c)] + other_visited[(nr, nc)]

💡 Bidirectional BFS efficiently finds shortest path by meeting in the middle.

reconstruct

Final state with answer

The shortest path length 2 is confirmed as the final answer.

💡 The algorithm successfully found the shortest path by meeting in the middle.

Line:

return res  # res = 2

💡 Bidirectional BFS reduces search space and finds shortest path efficiently.

from collections import deque
from typing import List

class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        n = len(grid)  # STEP 1
        if grid[0][0] != 0 or grid[n-1][n-1] != 0:  # STEP 1
            return -1
        directions = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)]  # STEP 2

        start_queue = deque([(0, 0)])  # STEP 2
        end_queue = deque([(n-1, n-1)])  # STEP 2
        start_visited = {(0, 0): 1}  # STEP 2
        end_visited = {(n-1, n-1): 1}  # STEP 2

        def visit(queue, visited, other_visited):  # STEP 3
            r, c = queue.popleft()  # STEP 3
            for dr, dc in directions:  # STEP 4-6
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
                    if (nr, nc) in other_visited:  # STEP 6
                        return visited[(r, c)] + other_visited[(nr, nc)]
                    if (nr, nc) not in visited:  # STEP 5
                        visited[(nr, nc)] = visited[(r, c)] + 1
                        queue.append((nr, nc))
            return None

        while start_queue and end_queue:  # STEP 7
            if len(start_queue) <= len(end_queue):
                res = visit(start_queue, start_visited, end_visited)
            else:
                res = visit(end_queue, end_visited, start_visited)
            if res is not None:
                return res
        return -1

📊

Shortest Path in Binary Matrix - Watch the Algorithm Execute, Step by Step

Watching the algorithm step through each node expansion and queue update reveals how bidirectional BFS efficiently finds the shortest path by meeting in the middle, which is hard to grasp from code alone.

Visiting: none

(0,0)

(0,1)

(1,0)

(1,1)

Visiting: none

(0,0)

(0,1)

(1,0)

(1,1)

Queue / Stack

(0,0)(1,1)

Visiting: (0,0)

(0,0)

(0,1)

(1,0)

(1,1)

Queue / Stack

(1,1)

Visiting: (0,0)

Edge: (0,0) → (0,1)

(0,0)

(0,1)

(1,0)

(1,1)

Queue / Stack

(1,1)

Visiting: (0,0)

Edge: (0,0) → (1,0)

(0,0)

(0,1)

(1,0)

(1,1)

Queue / Stack

(1,1)

Visiting: (0,0)

Edge: (0,0) → (1,1)

(0,0)

(0,1)

(1,0)

(1,1)

Queue / Stack

(1,1)

Visiting: (1,1)

(0,0)

(0,1)

(1,0)

(1,1)

Visiting: (1,1)

Edge: (1,1) → (0,0)

(0,0)

(0,1)

(1,0)

(1,1)

Visiting: none

(0,0)

(0,1)

(1,0)

(1,1)

Key Takeaways

✓ Bidirectional BFS reduces the search space by expanding from both start and end simultaneously.

This is hard to see from code alone because it requires visualizing two frontiers meeting in the middle.

✓ Blocked cells are skipped immediately, preventing invalid paths and pruning the search.

Watching each neighbor check clarifies how the algorithm avoids blocked cells.

✓ The shortest path length is the sum of distances from both ends to the meeting node.

This insight explains why the algorithm returns the sum of visited distances rather than just one side's distance.

Practice

1. Consider the following Python code implementing the Bellman-Ford algorithm for the Network Delay Time problem. Given the input times = [[1,2,1],[2,3,2],[1,3,4]], n = 3, and k = 1, what is the final returned value?

easy

A. 4

B. 3

C. 2

D. -1

Solution

1. Step 1: Initialize distances with dist[1]=0, dist[2]=inf, dist[3]=inf

   After first iteration, relax edges: dist[2]=1 (via 1->2), dist[3]=4 (via 1->3)

2. Step 2: Second iteration relaxes edge 2->3: dist[3] updated to dist[2]+2=3 which is less than 4

   No further updates after this iteration, so loop breaks early

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Maximum distance is 3, so return 3 [OK]

Hint: Relax edges repeatedly until no updates or n-1 iterations [OK]

Common Mistakes:

• Not updating dist[3] to 3 after second iteration
• Returning initial max distance 4 instead of updated 3
• Confusing iteration count and stopping early

2. Consider the following Python code that counts connected components using BFS. What is the value of count returned by countComponents(4, [[0,1],[2,3]])?

easy

A. 1

B. 2

C. 3

D. 4

Solution

1. Step 1: Trace BFS starting from node 0

   Nodes 0 and 1 are connected, so BFS visits both, marking them visited. This forms one component.

2. Step 2: Trace BFS starting from node 2

   Nodes 2 and 3 are connected, BFS visits both, marking them visited. This forms the second component.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Two disconnected pairs -> 2 components [OK]

Hint: Count increments once per unvisited node BFS start [OK]

Common Mistakes:

• Counting edges instead of components
• Off-by-one in count increment

3. Examine the following buggy flood fill code snippet. Which line contains the subtle bug that can cause infinite recursion or incorrect behavior?

medium

A. Line 6: checking if image[r][c] == newColor before recoloring

B. Line 2: missing check if original_color == newColor before starting

C. Line 8: recoloring pixel before checking neighbors

D. Line 11: boundary check for neighbors

Solution

1. Step 1: Identify missing early exit condition

   The code does not check if the starting pixel's color equals newColor before DFS, which can cause infinite recursion if they are equal.

2. Step 2: Verify other lines

   Line 6's check prevents revisiting recolored pixels, line 8 recolors before neighbors which is correct, and line 11 correctly checks boundaries.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Missing early exit causes infinite recursion on equal colors [OK]

Hint: Check if start pixel color equals newColor before DFS [OK]

Common Mistakes:

• Forgetting early exit causes infinite recursion
• Misplacing boundary checks

4. Suppose the star graph edges can be repeated multiple times (i.e., multi-edges allowed). Which modification to the frequency counting approach correctly finds the center node?

hard

A. Count frequencies as usual; the node with the highest frequency is the center, ignoring duplicates.

B. Use a set to track unique neighbors per node and find the node connected to all other distinct nodes.

C. Ignore frequency counts and perform BFS from node 1 to find the center.

D. Sort edges and pick the node appearing in the first edge as center.

Solution

1. Step 1: Understand multi-edge impact

   Repeated edges inflate frequency counts, so counting raw frequencies misidentifies the center.

2. Step 2: Track unique neighbors

   Using a set per node to count unique neighbors ensures duplicates don't skew counts; the center connects to all other distinct nodes.

3. Step 3: Identify center

   The node whose unique neighbor count equals n-1 is the center.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Counting unique neighbors handles multi-edges correctly [OK]

Hint: Count unique neighbors, not raw frequency [OK]

Common Mistakes:

• Ignoring duplicates and trusting raw frequency
• Assuming first edge node is center
• Using BFS unnecessarily

5. Suppose the graph may contain cycles. Which modification to the optimal algorithm is necessary to correctly find the minimal set of vertices to reach all nodes?

hard

A. Run the same topological sort algorithm; cycles do not affect the result.

B. Use BFS from each node to find reachability since topological sort fails.

C. Ignore in-degree and pick nodes with maximum out-degree instead.

D. Detect cycles first and return an error or handle strongly connected components.

Solution

1. Step 1: Understand cycle impact

   Topological sort requires DAGs; cycles prevent valid ordering and break the algorithm.

2. Step 2: Modify approach

   Detect cycles using DFS or union-find. For cyclic graphs, identify strongly connected components and treat them as single nodes or return error.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Cycle detection is essential before topological sort [OK]

Hint: Topological sort requires DAG; detect cycles first [OK]

Common Mistakes:

• Assuming topological sort works on cyclic graphs
• Ignoring cycles and returning incorrect minimal sets
• Using BFS from each node which is inefficient