Problem Statement

Shortest Path in Binary Matrix

You are given a square grid (n rows and n columns) where every cell is either a 0 (open, you can step on it) or a 1 (blocked, a wall). You start at the top-left cell and want to reach the bottom-right cell. You can move to any of the 8 neighbors of a cell, the four straight directions and the four diagonals. A clear path is a route that only steps on 0 cells. The answer is how many cells that shortest route touches, counting both the start and the end. If there is no way through, return -1.

mediumGraphBFSGraphsTime: O(n^2) · Space: O(n^2)

Signals to notice

shortest path in binary grid8-directional movementBFS from corner to corner

Brute force first

DFS trying all paths — doesn't find shortest path efficiently and revisits cells. It is a fair place to begin because it matches the surface of the question, yet it does not capture the deeper structure that makes the problem simpler.

The key insight

BFS from (0,0) to (n-1,n-1) allowing 8-directional movement. Only traverse 0-cells. The BFS level count gives the shortest path length. Instead of recomputing the world every time, you preserve just enough context to let the next decision become obvious.

Trace it on `grid=[[0,0,0],[1,1,0],[1,1,0]] (n=3, answer 4)`

Check start grid[0][0]=0 and end grid[2][2]=0: both clear. queue=[(0,0,1)], mark grid[0][0]=1
Pop (0,0,1). Not target. Scan 8 neighbors: only (0,1)=0 is valid. Mark it. queue=[(0,1,2)]
Pop (0,1,2). Not target. Valid 0-neighbors: (0,2) and (1,2). Mark both. queue=[(0,2,3),(1,2,3)]
Pop (0,2,3). Not target. (1,2) already visited; no new 0-cells. queue=[(1,2,3)]
Pop (1,2,3). Not target. Valid 0-neighbor: (2,2). Mark it. queue=[(2,2,4)]
Pop (2,2,4). r==n-1 and c==n-1 -> return dist = 4

What must stay true

BFS guarantees shortest path in an unweighted grid. 8-directional movement means each cell has up to 8 neighbors. The path length counts cells visited, including start and end. As long as that statement keeps holding, you can trust the steps built on top of it.

Shape of the loop

if start or end is blocked: return -1
queue = [(0, 0, dist=1)];  mark start visited
while queue:
    r, c, dist = popleft()
    if (r, c) is bottom-right: return dist
    for each of 8 neighbors (nr, nc) in-bounds and == 0:
        mark visited;  queue.append((nr, nc, dist + 1))
return -1

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Forgetting to check if start or end cell is blocked (value 1) — return -1 immediately if either is blocked. Most mistakes here are not about syntax; they come from losing track of what your state, pointer, or structure is supposed to mean.

Graphs Pattern