Shortest Path in Binary Matrix

📋

Shortest Path in Binary Matrix

Edge cases:

</>

IDE

def shortestPathBinaryMatrix(grid: List[List[int]]) -> int:public int shortestPathBinaryMatrix(int[][] grid)int shortestPathBinaryMatrix(vector<vector<int>>& grid)function shortestPathBinaryMatrix(grid)

def shortestPathBinaryMatrix(grid):
    # Write your solution here
    pass

class Solution {
    public int shortestPathBinaryMatrix(int[][] grid) {
        // Write your solution here
        return -1;
    }
}

#include <vector>
using namespace std;

int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
    // Write your solution here
    return -1;
}

function shortestPathBinaryMatrix(grid) {
    // Write your solution here
    return -1;
}

Common Bugs to Avoid

Wrong: -1 when path existsNot considering diagonal moves or incorrectly marking visited cells.✅ Include all 8 directions in neighbor exploration and mark visited cells when enqueued.

Wrong: Path length longer than shortestUsing greedy approach instead of BFS, leading to suboptimal path.✅ Implement BFS level order traversal to guarantee shortest path.

Wrong: Crash or exception on empty gridNo check for empty input before processing.✅ Add explicit check for empty grid and return -1 immediately.

Wrong: TLE on large inputsUsing DFS/backtracking exponential approach instead of BFS.✅ Use BFS with queue and visited set for O(n^2) time complexity.

✓

Test Cases

Focus on handling boundary conditions like empty or single cell grids.

Think about common algorithmic pitfalls like greedy traps and revisiting nodes.

Optimize your solution to BFS to handle large grids efficiently.

t1_01basic

Input{"grid":[[0,1],[1,0]]}

Expected2

⏱ Performance - must finish in 2000ms

The shortest path is (0,0) → (1,1) diagonally, length 2.

💡 Think about BFS traversal in 8 directions from the start cell.

💡 Check all neighbors including diagonals and track shortest distance.

💡 Use a queue and mark visited cells to avoid revisiting.

Why it failed: Incorrect output means BFS or neighbor checks are wrong; ensure you consider all 8 directions and mark visited properly.

✓ Correct BFS traversal and shortest path calculation.

t1_02basic

Input{"grid":[[0,0,0],[1,1,0],[1,1,0]]}

Expected5

⏱ Performance - must finish in 2000ms

Shortest path is (0,0) → (0,1) → (0,2) → (1,2) → (2,2), length 5 steps.

💡 Try BFS level order traversal to find shortest path length.

💡 Remember to include diagonal moves and avoid blocked cells.

💡 Track distance from start and stop when reaching bottom-right.

Why it failed: If output is wrong, likely missing diagonal moves or not updating distances correctly; fix BFS neighbor exploration and distance updates.

✓ Correctly finds shortest path with BFS including diagonals.

t2_01edge

Input{"grid":[]}

Expected-1

⏱ Performance - must finish in 2000ms

Empty grid means no path exists, return -1.

💡 Check if grid is empty or n=0 before processing.

💡 Return -1 immediately if no cells to traverse.

💡 Handle boundary condition for empty input explicitly.

Why it failed: Code crashes or returns wrong value on empty grid; add check for empty input and return -1.

✓ Properly handles empty grid input.

t2_02edge

Input{"grid":[[0]]}

Expected1

⏱ Performance - must finish in 2000ms

Single cell grid with 0 means start=end, path length is 1.

💡 Check if start and end are the same cell.

💡 If that cell is 0, shortest path length is 1.

💡 Return 1 immediately for single cell free grid.

Why it failed: Fails to handle single cell free grid; add condition to return 1 if start==end and cell is 0.

✓ Correctly returns 1 for single cell free grid.

t2_03edge

Input{"grid":[[1]]}

Expected-1

⏱ Performance - must finish in 2000ms

Single cell grid blocked means no path, return -1.

💡 Check if start or end cell is blocked (value 1).

💡 If blocked, return -1 immediately.

💡 Handle single cell blocked case explicitly.

Why it failed: Fails to detect blocked start/end cell; add check grid[0][0] and grid[n-1][n-1] == 0 before BFS.

✓ Correctly returns -1 for blocked single cell grid.

t2_04edge

Input{"grid":[[0,0],[0,0]]}

Expected2

⏱ Performance - must finish in 2000ms

Small grid with all zeros; shortest path is diagonal (0,0) → (1,1), length 2.

💡 Check that diagonal moves are allowed and counted.

💡 Use BFS to find shortest path in all 8 directions.

💡 Return the shortest distance when reaching bottom-right.

Why it failed: Fails to consider diagonal moves; fix BFS neighbor exploration to include diagonals.

✓ Correctly finds shortest path using diagonals.

t3_01corner

Input{"grid":[[0,0,0],[0,1,0],[0,0,0]]}

Expected4

⏱ Performance - must finish in 2000ms

Shortest path avoids blocked center cell using diagonals, length 4.

💡 Beware of greedy approaches that pick first available neighbor.

💡 Use BFS to explore all neighbors to find shortest path.

💡 Avoid greedy; BFS ensures shortest path even if detours needed.

Why it failed: Greedy approach fails by choosing blocked or longer path; fix by implementing BFS with queue and visited set.

✓ BFS correctly finds shortest path avoiding blocked cells.

t3_02corner

Input{"grid":[[0,0,0,0],[1,1,1,0],[0,0,0,0],[0,1,1,1],[0,0,0,0]]}

Expected8

⏱ Performance - must finish in 2000ms

Path requires careful BFS to navigate around blocked cells, length 8.

💡 Check that you do not revisit cells or count paths incorrectly.

💡 Ensure BFS marks visited cells immediately when enqueued.

💡 Use 8-direction BFS with visited to avoid infinite loops and wrong counts.

Why it failed: Incorrect path length due to revisiting cells or incorrect distance updates; fix by marking visited on enqueue, not dequeue.

✓ Correct BFS with visited marking finds shortest path length.

t3_03corner

Input{"grid":[[0,1,0],[1,0,1],[0,1,0]]}

Expected-1

⏱ Performance - must finish in 2000ms

No path exists due to blocking pattern, return -1.

💡 Check if BFS exhausts all reachable cells without reaching end.

💡 Return -1 if no path found after BFS completes.

💡 Ensure BFS terminates correctly and returns -1 if unreachable.

Why it failed: Fails to return -1 when no path exists; add condition to return -1 if BFS queue empties without reaching end.

✓ Correctly returns -1 when no path is possible.

t4_01performance

Input{"grid":[[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]]}

Expectednull

⏱ Performance - must finish in 2000ms

n=100 grid with alternating blocked rows; BFS O(n^2) must complete within 2s.

💡 Use BFS with queue and visited to achieve O(n^2) time complexity.

💡 Avoid DFS or backtracking which is exponential and will TLE.

💡 Mark visited cells when enqueued to prevent redundant processing.

Why it failed: TLE occurs if using DFS/backtracking or inefficient neighbor checks; fix by implementing BFS with proper pruning and visited marking.

✓ Efficient BFS with O(n^2) complexity confirmed.

Practice

1. Given the following Python code implementing the two-pass DP solution for the 01 Matrix problem, what is the final distance matrix returned for input [[0,1,1],[1,1,0],[1,1,1]]?

easy

A. [[0,1,1],[1,1,0],[2,1,1]]

B. [[0,1,2],[1,1,0],[2,1,1]]

C. [[0,1,1],[1,2,0],[2,1,1]]

D. [[0,1,1],[1,1,0],[1,1,1]]

Solution

1. Step 1: Initialize distances

   Set dist to 0 where mat is 0, else infinity: [[0,inf,inf],[inf,inf,0],[inf,inf,inf]]

2. Step 2: Forward pass updates

   Update dist using top and left neighbors: [[0,1,2],[1,2,0],[2,3,1]]

3. Step 3: Backward pass updates

   Update dist using bottom and right neighbors: [[0,1,2],[1,1,0],[2,1,1]]

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Distances match shortest paths to nearest zero [OK]

Hint: Two-pass DP updates distances from neighbors correctly [OK]

Common Mistakes:

• Off-by-one in indices
• Forgetting backward pass
• Incorrect initialization

2. 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

3. You are given a 2D grid map of '1's (land) and '0's (water). You need to count the number of distinct islands, where an island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. Which algorithmic approach guarantees an optimal solution to this problem?

easy

A. Use Depth-First Search (DFS) or Breadth-First Search (BFS) to traverse connected components in the grid.

B. Use a sorting-based approach to group land cells and count islands.

C. Use Dynamic Programming to store intermediate island counts for subgrids.

D. Use a greedy approach to count islands by scanning rows and columns independently.

Solution

1. Step 1: Understand the problem as finding connected components in a grid

   The problem requires identifying groups of adjacent '1's connected horizontally or vertically, which is a classic graph traversal problem.

2. Step 2: Recognize that DFS or BFS traversals efficiently explore connected components

   DFS or BFS starting from each unvisited land cell will mark all connected land cells as visited, ensuring each island is counted exactly once.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DFS/BFS is the standard approach for connected components in grids [OK]

Hint: Islands = connected components -> use DFS/BFS [OK]

Common Mistakes:

• Thinking greedy or sorting can identify islands correctly.

4. Consider the following Python code implementing bidirectional BFS for the Word Ladder problem. Given beginWord = "hit", endWord = "cog", and wordList = ["hot", "dot", "dog", "lot", "log", "cog"], what is the returned value?

easy

A. 4

B. 5

C. 6

D. 0

Solution

1. Step 1: Trace initial sets and level

   begin_set = {"hit"}, end_set = {"cog"}, level = 1

2. Step 2: Expand begin_set neighbors and check for intersection

   Level 2: neighbors of "hit" include "hot"; no intersection yet. Level increments to 2.

3. Step 3: Expand smaller frontier each iteration until intersection

   Level 3: from "hot" neighbors "dot", "lot"; still no intersection. Level 4: from "dot", "lot" neighbors "dog", "log"; next level neighbors include "cog" which is in end_set, so return level + 1 = 4.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Shortest transformation length is 4 steps [OK]

Hint: Bidirectional BFS returns shortest path length 4 [OK]

Common Mistakes:

• Off-by-one in level counting
• Not updating visited correctly
• Returning 0 if endWord missing

5. Suppose the flood fill problem is modified so that pixels can be recolored multiple times if they become connected again after recoloring neighbors (e.g., due to dynamic color changes). Which modification to the algorithm is necessary to handle this correctly?

hard

A. Implement a queue-based BFS with a visited set to track pixels to recolor multiple times safely

B. Remove the early exit check for original_color == newColor to allow recoloring cycles

C. Use a visited set to prevent recoloring any pixel more than once

D. Allow recoloring pixels multiple times without tracking visited, relying on recursion depth

Solution

1. Step 1: Understand the problem variant

   Pixels can be recolored multiple times if connectivity changes dynamically, so simple DFS with early exit is insufficient.

2. Step 2: Choose an approach that tracks pixels safely

   BFS with a visited set can manage dynamic recoloring by controlling which pixels are processed and preventing infinite loops.

3. Step 3: Explain why other options fail

   Use a visited set to prevent recoloring any pixel more than once disallows multiple recolors, B removes necessary early exit causing infinite loops, D risks infinite recursion without control.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   BFS with visited set handles dynamic recoloring safely [OK]

Hint: Dynamic recoloring needs careful tracking with BFS and visited set [OK]

Common Mistakes:

• Removing early exit causes infinite loops
• Ignoring visited set leads to stack overflow