Shortest Path in a Binary Matrix With Eight Directions

If you interview at Meta, Amazon, Google, expect some version of "Shortest Path in Binary Matrix". It is rated Medium, and it falls squarely into the Tree BFS pattern — pattern-first preparation beats grinding random problems every time. Part 10 of 11 in the Tree BFS arc.

The Problem

In an n x n binary grid, return the length of the shortest clear path from the top-left to the bottom-right cell, moving in 8 directions through 0-cells only; -1 if none exists. Path length counts cells, not steps. The purest shortest-path-equals-BFS question in the set.

Input:  grid = [[0, 0, 0], [1, 1, 0], [1, 1, 0]]
Output: 4

Recognizing the Tree BFS Pattern

Breadth-first search explores a tree or graph level by level using a queue, and its defining superpower is the level snapshot: freeze the queue length, process exactly that many nodes, and you have processed one complete level. Anything phrased per-level — level lists, level averages, rightmost visible node, shortest path in unweighted structures — is BFS by construction.

Unweighted grid, shortest path: BFS explores in increasing distance order, so the first arrival at the target is optimal — no Dijkstra needed when every edge costs one. DFS finds a path; only BFS certifies the shortest. Say that sentence; it is the question.

The Approach

Enqueue the start with distance 1 (cells, per the spec). Pop, expand all eight neighbors that are in-bounds, clear, and unvisited — marking visited at enqueue time. Return the distance upon popping (or enqueueing) the target.

Check the two corner cells first: a blocked start or end is an immediate -1, and the 1 x 1 grid with a clear cell returns 1. Interviewers seed both.

Python Solution

from collections import deque


def shortest_path_binary_matrix(grid: list[list[int]]) -> int:
    """Cells on the shortest 8-directional clear path, else -1."""
    n = len(grid)
    if grid[0][0] or grid[n - 1][n - 1]:
        return -1
    queue: deque[tuple[int, int, int]] = deque([(0, 0, 1)])
    grid[0][0] = 1                          # reuse the grid as visited
    while queue:
        r, c, dist = queue.popleft()
        if r == n - 1 and c == n - 1:
            return dist
        for dr in (-1, 0, 1):
            for dc in (-1, 0, 1):
                if dr == 0 and dc == 0:
                    continue
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
                    grid[nr][nc] = 1        # mark at enqueue time
                    queue.append((nr, nc, dist + 1))
    return -1

Complexity

• Time: O(n²) — each cell enters the queue at most once, eight neighbor checks each
• Space: O(n²) — queue in the worst case; visited marks reuse the grid

Interview Tips and Follow-Ups

• Mark visited at enqueue, not at pop — with eight directions the duplicate-enqueue blowup is dramatic enough to time out.
• If asked to preserve the input, a separate visited set is the honest cost — O(n²) extra. Trade-offs beat silent mutation.
• Escalate to weighted cells and the answer becomes Dijkstra; to unit weights with 0/1 costs, 0-1 BFS with a deque. Name the ladder.

If this clicked, continue the Tree BFS arc in the Technical Interview category. One hundred questions, nine patterns, all in Python.