Shortest Path in Binary Matrix — 8-Directional BFS (LC 1091)

Problem Statement#

LeetCode 1091 — Shortest Path in Binary Matrix (Medium)

Given an n x n binary matrix grid, return the length of the shortest clear path in the matrix. If there is no clear path, return -1.

A clear path is a path from (0, 0) to (n-1, n-1) such that:

• All visited cells are 0.
• All adjacent cells in the path are connected 8-directionally (the cell shares a side or corner).

The length of a clear path is the number of visited cells.

Constraints:

• n == grid.length == grid[i].length
• 1 <= n <= 100
• grid[i][j] is 0 or 1.

Example:

Input: grid = [[0,0,0],
               [1,1,0],
               [1,1,0]]
Output: 4
Explanation: Path is (0,0)->(0,1)->(0,2)->(1,2)->(2,2). Length = 4 cells.
 
Input: grid = [[1,0,0],...]
Output: -1
Explanation: Start cell is blocked.

Why This Problem Matters#

Shortest Path in Binary Matrix is the purest BFS interview problem on a grid. There are no twists — no multi-source seeding, no level-counting beyond what BFS gives for free, no clever inversion. It tests a single skill: do you know that BFS finds shortest paths in unweighted graphs and can you implement it without a bug?

This makes it a perfect Phase-1 grid problem at Google, Amazon, and Meta. The 8-directional twist (instead of the standard 4) is small but trips many candidates who hard-code the four cardinal deltas. The unreachable case (-1) is another classic graded behavior. Mastering this problem locks in the BFS template you will reuse on LC 994, LC 542, LC 286, and many more.

The Core Insight#

Because every step has weight 1, BFS from the start cell guarantees that the first time we dequeue the destination, we have found the shortest path. There is no need for Dijkstra, no need for A* unless interview asks for it.

The mechanics:

1. Edge case the start and end: if either is 1, return -1.
2. BFS from (0, 0) with distance 1 (the start cell counts).
3. Eight directional deltas: (dr, dc) for every combination of {-1, 0, 1} except (0, 0).
4. Mark cells as visited by flipping them to 1 in-place (or use a separate set).
5. Return the distance when the destination is dequeued.

Why BFS, not DFS? DFS does not yield shortest paths in general graphs without iterative deepening. BFS's level-by-level expansion is exactly the shortest-path guarantee on unweighted graphs.

Optimization: A*. Using Manhattan-or-Chebyshev distance as a heuristic prunes the search and is sometimes asked as a follow-up. For typical interview constraints (n <= 100), plain BFS is sufficient.

Visual Dry Run#

Grid:

0 0 0
1 1 0
1 1 0

Start (0,0) enqueued with distance 1.

Answer: 4.

Solution (Optimal)#

Python#

from collections import deque
 
class Solution:
    def shortestPathBinaryMatrix(self, grid: list[list[int]]) -> int:
        N = len(grid)
        # edge case: start or end blocked
        if grid[0][0] == 1 or grid[N - 1][N - 1] == 1:
            return -1
 
        directions = [(-1, -1), (-1, 0), (-1, 1),
                      (0, -1),           (0, 1),
                      (1, -1),  (1, 0),  (1, 1)]
        queue = deque([(0, 0, 1)])               # row, col, distance
        grid[0][0] = 1                           # mark visited
 
        while queue:
            r, c, d = queue.popleft()
            if r == N - 1 and c == N - 1:
                return d
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < N and 0 <= nc < N and grid[nr][nc] == 0:
                    grid[nr][nc] = 1             # mark before enqueue (avoid duplicates)
                    queue.append((nr, nc, d + 1))
        return -1

JavaScript#

/**
 * @param {number[][]} grid
 * @return {number}
 */
var shortestPathBinaryMatrix = function(grid) {
    const N = grid.length;
    if (grid[0][0] === 1 || grid[N - 1][N - 1] === 1) return -1;
 
    const dirs = [[-1, -1], [-1, 0], [-1, 1],
                  [0, -1],           [0, 1],
                  [1, -1],  [1, 0],  [1, 1]];
 
    const queue = [[0, 0, 1]];                   // row, col, distance
    grid[0][0] = 1;
    let head = 0;                                // pointer dequeue for O(1)
 
    while (head < queue.length) {
        const [r, c, d] = queue[head++];
        if (r === N - 1 && c === N - 1) return d;
        for (const [dr, dc] of dirs) {
            const nr = r + dr, nc = c + dc;
            if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
            if (grid[nr][nc] !== 0) continue;
            grid[nr][nc] = 1;                    // mark visited immediately
            queue.push([nr, nc, d + 1]);
        }
    }
    return -1;
};

Time Complexity: O(n^2) — each cell enqueued at most once. Space Complexity: O(n^2) for the queue worst case.

Common Mistakes#

1. Returning d - 1. The problem counts cells in the path, not edges. Distance is initialized to 1 because the start cell counts.
2. Using only 4 directions. The problem explicitly allows diagonal moves. Forgetting causes wrong answers on obvious test cases.
3. Marking visited after dequeue, not before enqueue. This permits the same cell to be enqueued multiple times before the first dequeue, blowing up memory and time on adversarial grids.
4. Skipping the start/end blocked check. Both (0,0) and (n-1, n-1) must be 0. If either is 1, return -1 immediately.
5. Using DFS to find shortest path. Without explicit relaxation, DFS may find a path but not the shortest one.

Interview Tips#

• Articulate the BFS guarantee. "Because every edge has the same weight, BFS finds the shortest path in O(V + E) time."
• Explicitly state 8-directional moves. Many candidates default to 4 — saying "8 deltas including diagonals" shows attention to spec.
• Discuss A*. As a follow-up, mention "Chebyshev distance is an admissible heuristic since one diagonal step costs 1 unit". Even if you do not implement it, mentioning it shows depth.
• Mention bidirectional BFS for very large grids: search from both ends until they meet — halves the explored area.

Follow-up Questions#

1. What if cells have weights (e.g., terrain difficulty)? Use Dijkstra's algorithm with a min-heap.
2. What if there are multiple sources or destinations? Multi-source BFS still works; seed the queue with all starts.
3. A with a heuristic?* Chebyshev distance to the destination is admissible for 8-directional moves; use it to guide a priority queue.
4. Bidirectional BFS? Run BFS from start and from end alternately; when their frontiers meet, sum the distances.
5. Path reconstruction? Maintain a parent pointer from each cell; once the destination is reached, walk parents back to start.

Key Takeaways#

• Shortest Path in Binary Matrix is the textbook BFS application: unweighted graph, single-source, single-target.
• Use 8 directional deltas — the diagonal moves are mandatory.
• Mark cells visited before enqueueing, not after dequeuing, to avoid duplicate work.
• Distance counts cells, not edges; initialize the start at 1.
• Return -1 when the queue empties without reaching the destination — and check start/end blocked cells upfront.
• BFS is O(n^2) here; A*, bidirectional BFS, and Dijkstra are valuable follow-up topics.