Shortest Path in Binary Matrix

Shortest Path in Binary Matrix

What is this problem about?

The Shortest Path in Binary Matrix interview question gives you an n×n binary matrix where 0 represents open cells and 1 represents blocked cells. Find the length of the shortest clear path from the top-left corner (0,0) to the bottom-right corner (n-1, n-1), moving in any of 8 directions (including diagonals). If no clear path exists, return -1. A clear path must pass through only 0-valued cells, and the start and end must also be 0.

Why is this asked in interviews?

Uber, Goldman Sachs, Microsoft, Meta, Amazon, Google, and Bloomberg ask this problem because it is the canonical 8-directional BFS on a binary grid. It extends the standard 4-directional BFS with diagonal movement, making path planning more realistic (applicable to robot navigation, game AI pathfinding, and network routing). It tests BFS implementation, grid boundary checking, and the 8-direction delta array.

Algorithmic pattern used

The pattern is BFS with 8-directional movement. If the start or end cell is 1, return -1 immediately. Initialize BFS queue with (0, 0, distance=1). Mark (0,0) as visited. For each cell, try all 8 directions using delta pairs: (-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1). For each valid unvisited 0-neighbor, add to queue with distance+1. Return the distance when (n-1, n-1) is reached.

Example explanation

Grid:

0 0 0
1 1 0
1 1 0

BFS from (0,0):

• Level 1: (0,0). Distance=1.
• Level 2: (0,1). Distance=2.
• Level 3: (0,2),(1,2). Distance=3.
• Level 4: (2,2). Distance=4.

But diagonal: (0,0)→(0,1)→(1,2)→(2,2): path length 4. Or (0,0)→(0,1)→(0,2)→(1,2)→(2,2): 5. With diagonal move: (0,1)→(1,2) is diagonal, distance 3; then (2,2) at 4.

Shortest: 4 (0,0→0,1→0,2→1,2→2,2 = 5 without diagonal; with diagonal (0,0)→(0,1)→(1,2)→(2,2) = 4).

Common mistakes candidates make

• Using only 4-directional movement — this problem requires 8-direction movement including diagonals.
• Not checking if the start or end cell is 1 before starting BFS — return -1 immediately in that case.
• Revisiting cells — mark cells as visited when adding to the queue, not when processing.
• Counting the path length as number of edges instead of number of cells — the problem counts cells including start and end.

Interview preparation tip

For the Shortest Path in Binary Matrix coding problem, the BFS matrix interview pattern with 8-directional movement is standard. The 8-direction delta array [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)] is worth memorizing for diagonal BFS problems. Goldman Sachs and Palo Alto Networks interviewers often ask follow-ups: "What if diagonal moves cost 2 instead of 1?" — switch to Dijkstra. Practice BFS path-length counting (cells, not edges) — it's a common source of off-by-one errors.