Shortest Path in Binary Matrix: BFS on an 8-Directional Grid
Solve Shortest Path in Binary Matrix with breadth-first search on an 8-directional grid — intuition, JavaScript code, a full walkthrough, and O(n²) complexity.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
A grid of zeros and ones. Zeros are floor, ones are walls, and you want the shortest walk from the top-left corner to the bottom-right — moving in any of the eight compass directions, diagonals included. That's Shortest Path in Binary Matrix.
The twist that trips people up is the word shortest. Depth-first search will happily find a path, but it has no idea whether it's the best one. To get the minimum every time, you need a traversal that explores the grid in rings of increasing distance. That's breadth-first search, and this problem is one of the cleanest places to see why BFS and "shortest path in an unweighted graph" are the same idea.
Get the reasoning here and you own a template that reappears in mazes, flood fills, word ladders, and rotting-oranges-style spread problems.
The problem
Given an n x n binary matrix grid, return the length of the shortest clear path from the top-left cell (0, 0) to the bottom-right cell (n-1, n-1). A clear path only steps on cells valued 0, and each step may move to any of the 8 adjacent cells (up, down, left, right, and the four diagonals). The path length is the number of cells visited, not the number of moves. If no clear path exists, return -1.
Input: grid = [[0, 0, 0],
[1, 1, 0],
[1, 1, 0]]
Output: 4
Path: (0,0) -> (0,1) -> (1,2) -> (2,2) // 4 cellsTwo rules quietly shape everything:
- The start
(0,0)and the target(n-1,n-1)must both be0. If either is a wall, the answer is-1before you take a single step. - Length counts cells, so a single-cell
[[0]]grid has a path of length1, not0. The distance of the start cell is 1.
The brute force baseline
The instinct is to explore every route with recursion, backtracking whenever you hit a wall or the edge, and keep the shortest completed path.
function shortestPathBruteForce(grid) {
const N = grid.length;
if (grid[0][0] !== 0 || grid[N - 1][N - 1] !== 0) return -1;
let best = Infinity;
const seen = Array.from({ length: N }, () => Array(N).fill(false));
function dfs(r, c, len) {
if (r < 0 || r >= N || c < 0 || c >= N) return;
if (grid[r][c] === 1 || seen[r][c]) return;
if (r === N - 1 && c === N - 1) { best = Math.min(best, len + 1); return; }
seen[r][c] = true;
for (const [dr, dc] of DIRS) dfs(r + dr, c + dc, len + 1);
seen[r][c] = false; // backtrack
}
dfs(0, 0, 0);
return best === Infinity ? -1 : best;
}It's correct, but it re-walks the same cells through countless different routes. Because it tries every possible ordering of moves, the running time is exponential in the number of open cells — an 8×8 grid can blow up into millions of partial paths. Worse, it only knows a path was shortest after exploring all of them. BFS gets the same answer while touching each cell once.
The key insight: BFS explores in distance rings
Model the grid as an unweighted graph: each open cell is a node, and an edge connects two cells if they're 8-directionally adjacent. Every move costs exactly 1.
In a graph where every edge has the same weight, breadth-first search visits nodes in order of their distance from the source. It drains all cells at distance 1, then all cells at distance 2, and so on. So the first time BFS touches the target, it does so along a shortest path — there is no shorter route still hiding in the queue, because the queue is strictly ordered by distance.
That's the whole trick. Use a FIFO queue, record each cell's distance the moment you enqueue it, and the answer falls out the instant you dequeue the target. No path ever needs re-examining, because a cell's first-recorded distance is already its minimum.
The optimal solution
Here's the BFS the visualizer traces, cell by cell. The distGrid does double duty: it stores each cell's distance and acts as the visited set — a value of -1 means unvisited.
function shortestPathBinaryMatrix(grid) {
const N = grid.length;
// Edge case: start or end is blocked
if (grid[0][0] !== 0 || grid[N - 1][N - 1] !== 0) return -1;
if (N === 1) return 1;
// Queue stores coords [row, col]
const queue = [[0, 0]];
// Distance grid doubles as the visited set (-1 = unvisited)
const distGrid = Array.from({ length: N }, () => Array(N).fill(-1));
distGrid[0][0] = 1;
// 8-directional moves
const dirs = [
[-1, -1], [-1, 0], [-1, 1],
[ 0, -1], [ 0, 1],
[ 1, -1], [ 1, 0], [ 1, 1],
];
while (queue.length > 0) {
const [r, c] = queue.shift();
const currentDist = distGrid[r][c];
if (r === N - 1 && c === N - 1) return currentDist;
for (const [dr, dc] of dirs) {
const nr = r + dr;
const nc = c + dc;
if (nr >= 0 && nr < N && nc >= 0 && nc < N
&& grid[nr][nc] === 0
&& distGrid[nr][nc] === -1) {
distGrid[nr][nc] = currentDist + 1;
queue.push([nr, nc]);
}
}
}
return -1; // queue drained, target never reached
}Three details make it correct:
- Distance starts at 1.
distGrid[0][0] = 1because the problem counts cells. When the target is reached,currentDistis already the cell count. - Mark visited at enqueue, not dequeue. Setting
distGrid[nr][nc]the moment you push guarantees a cell is queued exactly once. Defer it to dequeue time and duplicates pile up, inflating the runtime. - The 8-direction array includes diagonals, so cells can slip past walls that a 4-directional grid would trap you behind.
Walkthrough
Trace grid = [[0,0,0],[1,1,0],[1,1,0]] (N = 3). The queue holds [r,c] coordinates; every enqueued cell records its distance immediately.
| Dequeue | Dist | New cells enqueued (with dist) | Queue after |
|---|---|---|---|
| — (init) | — | [0,0] → dist 1 | [[0,0]] |
[0,0] | 1 | [0,1] → dist 2 (right; [1,0],[1,1] are walls) | [[0,1]] |
[0,1] | 2 | [0,2] → dist 3, [1,2] → dist 3 | [[0,2],[1,2]] |
[0,2] | 3 | none (all neighbors visited, walls, or out of bounds) | [[1,2]] |
[1,2] | 3 | [2,2] → dist 4 (target enqueued) | [[2,2]] |
[2,2] | 4 | r === N-1 && c === N-1 → return 4 | — |
Notice [0,2] at distance 3 adds nothing new — its only open neighbors, [0,1] and [1,2], were already recorded. That's BFS refusing to re-visit, which is exactly what keeps it linear in the grid size. The target [2,2] first gets its distance (4) while [1,2] is being processed, and the algorithm returns the moment [2,2] is dequeued.
Complexity
Let n be the side length, so the grid holds n² cells.
| Approach | Time | Space | Why |
|---|---|---|---|
| DFS / backtracking | Exponential | O(n²) | tries every ordering of moves through open cells |
| BFS | O(n²) | O(n²) | each cell enqueued once; 8 constant-time neighbor checks per cell |
Every cell enters the queue at most once, and processing it does a fixed 8 neighbor checks — so the work is proportional to the number of cells, O(n²). The space is the distGrid plus a queue that can hold up to O(n²) cells in the worst case (a wide-open grid).
One footnote: this version uses queue.shift(), which is O(n²) per call in JavaScript because it re-indexes the array. On large grids, a pointer-based queue (an index into an array you never splice) or a deque keeps the overall bound at a clean O(n²).
Common mistakes
- Using DFS and hoping the first path is shortest. DFS finds a path, not the shortest one. On an unweighted grid, only BFS's distance-ring order guarantees minimality.
- Only checking 4 directions. This problem is explicitly 8-directional. Miss the diagonals and you'll report longer paths — or
-1on grids that clearly have a diagonal route. - Counting edges instead of cells. Start the distance at 1, not 0. A
[[0]]grid answers1. - Forgetting to validate start and end. If
grid[0][0]orgrid[n-1][n-1]is1, return-1immediately — otherwise you enqueue a blocked start or chase an unreachable target. - Marking visited on dequeue. Mark a cell the instant you enqueue it. Waiting until you pop it lets the same cell get queued several times before its first processing, breaking the once-per-cell guarantee.
Where this pattern shows up next
Grid BFS and its "first arrival is shortest" guarantee generalize well beyond mazes:
- Word Ladder — the same BFS layering, but the graph is words connected by single-letter edits instead of adjacent cells.
- Swim in Rising Water — grid traversal where edges gain weights, pushing you from plain BFS toward a priority queue.
- Reconstruct Itinerary — a graph-traversal cousin that swaps shortest-path BFS for an Eulerian-path DFS.
- Breadth First Search (BFS) — the pattern in its pure form, the foundation this problem is built on.
You can also step through the BFS interactively to watch the frontier queue fill and the distance rings spread across the grid, one cell at a time.
FAQ
Why does this problem require BFS instead of DFS?
Because it asks for the shortest path on an unweighted grid, and BFS is the only traversal that visits cells in strict order of distance from the start. It empties all cells one step away, then all cells two steps away, so the first time it reaches the target it has already found the minimum. DFS dives down one branch to the end before exploring alternatives, so its first path to the target is almost never the shortest — you'd have to enumerate every path and compare, which is exponentially slower.
What is the time and space complexity?
Both are O(n²) for an n x n grid. Each of the n² cells is enqueued at most once, and processing a cell checks a fixed 8 neighbors, so total work scales with the cell count. Space is O(n²) for the distance grid that doubles as the visited set, plus a queue that can hold up to O(n²) cells in the worst case of a wide-open grid.
Why does the distance start at 1 instead of 0?
The problem defines path length as the number of cells on the path, not the number of moves between them. A path through 4 cells has length 4 even though it only takes 3 moves. Setting distGrid[0][0] = 1 bakes that counting rule in from the start, so when BFS reaches the target the recorded distance is already the correct cell count with no +1 adjustment.
How do I handle the case where no path exists?
Two checks cover it. First, if the start (0,0) or the end (n-1,n-1) is a wall (1), return -1 up front. Second, if BFS drains its entire queue without ever dequeuing the target, every reachable open cell has been explored and none connect to the destination — so the loop exits and you return -1. Walls that fully surround the target trigger this second path.
Can I move only in 4 directions for this problem?
No. Shortest Path in Binary Matrix explicitly allows all 8 directions, including the four diagonals. The direction array must contain the diagonal offsets [-1,-1], [-1,1], [1,-1], and [1,1] alongside the cardinal moves. Diagonals let a path cut corners around walls, so a 4-directional version would return a longer distance or wrongly report -1 on grids that have a valid diagonal route.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.