Shortest Path in Binary Matrix

The problem. You're given an n × n grid of 0 (open) and 1 (blocked). Find the length of the shortest path from the top-left cell to the bottom-right cell that only steps on 0s. A step may go to any of the 8 neighbouring cells, diagonals included. The length counts the cells on the path. Return -1 if there is no such path.

Example

grid = [[0,1],
        [1,0]]          ->  2    (one diagonal step)

grid = [[0,0,0],
        [1,1,0],
        [1,1,0]]        ->  4    ((0,0) -> (0,1) -> (1,2) -> (2,2))

grid = [[1,0,0],
        [1,1,0],
        [1,1,0]]        ->  -1   (the start itself is blocked)

The pattern: shortest path with BFS

When every step costs the same, the shortest path is the one with the fewest steps — and BFS finds it for free. BFS visits the start, then everything 1 step away, then everything 2 steps away, and so on, ring by ring. So the first time it reaches a cell, it has come by a shortest route. Record that distance and never touch the cell again.

Any "fewest moves" question fits: moves in a grid, letter changes in a word, turns of a lock, knight jumps. Find the states, find what one move does, and BFS from the start until you meet the target. (When steps cost different amounts, BFS stops working — that's Dijkstra, Pattern 8.)

1. Brute force: try every path with DFS

Walk every simple path from the start with backtracking, and keep the shortest one that reaches the end. Skip a path as soon as it's no shorter than the best found.

1const DIRS = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]];2 3function shortestPathBinaryMatrix(grid) {4  const n = grid.length;5  let best = Infinity;6  const onPath = grid.map((row) => row.map(() => false));7  const walk = (r, c, length) => {8    if (r < 0 || r >= n || c < 0 || c >= n || grid[r][c] === 1 || onPath[r][c]) return;9    if (length >= best) return;             // can't beat the best path found so far10    if (r === n - 1 && c === n - 1) {11      best = length;12      return;13    }14    onPath[r][c] = true;15    for (const [dr, dc] of DIRS) walk(r + dr, c + dc, length + 1);16    onPath[r][c] = false;                   // free the cell for other paths17  };18  walk(0, 0, 1);19  return best === Infinity ? -1 : best;20}

Time exponential, space O(n²). The number of simple paths through an open grid grows explosively; even with the cut-off, a big empty grid is hopeless. DFS dives down one long path first, so it can't know a short one exists until it has wasted time on the long ones.

2. BFS from the start

Give the start distance 1 and put it in a queue. Each cell taken from the queue gives its open, unreached neighbours its distance plus one. The moment the bottom-right cell comes out of the queue, its distance is the answer.

1const DIRS = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]];2 3function shortestPathBinaryMatrix(grid) {4  const n = grid.length;5  if (grid[0][0] === 1 || grid[n - 1][n - 1] === 1) return -1;   // blocked start or end6  const dist = grid.map((row) => row.map(() => 0));   // 0: not reached yet7  dist[0][0] = 1;                           // a path's length counts cells, so the start is 18  const queue = [[0, 0]];9  let head = 0;10  while (head < queue.length) {11    const [r, c] = queue[head++];12    if (r === n - 1 && c === n - 1) return dist[r][c];   // first arrival = shortest13    for (const [dr, dc] of DIRS) {14      const nr = r + dr, nc = c + dc;15      if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] === 0 && dist[nr][nc] === 0) {16        dist[nr][nc] = dist[r][c] + 1;      // one cell further than the cell that found it17        queue.push([nr, nc]);18      }19    }20  }21  return -1;                                // the queue ran dry: no way through22}

Time O(n²), space O(n²). Each of the n² cells enters the queue at most once and checks 8 neighbours. The dist grid doubles as the visited marker.

Comparing the approaches

This is the most common mistake in graph interviews: reaching for DFS to find a shortest path. DFS finds a path; BFS finds the shortest one, because it explores in order of distance.

Edge cases to test

Variations