Skip to main content

1091. Shortest Path in Binary Matrix

mediumAsked at DoorDash

Find the length of the shortest clear path from top-left to bottom-right in a 0/1 grid, moving in 8 directions. DoorDash uses this as the canonical BFS-on-grid question — they want a clean queue with 8-directional moves, NOT DFS.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in DoorDash loops.

  • Glassdoor (2026-Q1)— DoorDash SWE onsite reports cite Shortest Path in Binary Matrix as a recurring BFS-on-grid question.
  • Blind (2025-11)— DoorDash new-grad reports note the 8-directional gotcha as a common bug.

Problem

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 in a binary matrix is a path from the top-left cell (i.e., (0, 0)) to the bottom-right cell (i.e., (n - 1, n - 1)) such that: all the visited cells of the path are 0, and all the adjacent cells of the path are 8-directionally connected. The length of a clear path is the number of visited cells of this path.

Constraints

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

Examples

Example 1

Input
grid = [[0,1],[1,0]]
Output
2

Example 2

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

Example 3

Input
grid = [[1,0,0],[1,1,0],[1,1,0]]
Output
-1

Explanation: Start cell is 1.

Approaches

1. BFS (optimal)

BFS from (0, 0). Visit 8 neighbors per cell. Track distance from start; return distance when you reach (n-1, n-1).

Time
O(n^2)
Space
O(n^2)
function shortestPathBinaryMatrix(grid) {
  const n = grid.length;
  if (grid[0][0] !== 0 || grid[n-1][n-1] !== 0) 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]];
  grid[0][0] = 1;
  while (queue.length) {
    const [r, c, d] = queue.shift();
    if (r === n - 1 && c === n - 1) return d;
    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) {
        grid[nr][nc] = 1;
        queue.push([nr, nc, d + 1]);
      }
    }
  }
  return -1;
}

Tradeoff: DoorDash's preferred answer. BFS guarantees shortest path in an unweighted grid. Mutating grid in place saves O(n^2) extra visited set.

2. A* search

Priority queue ordered by f = g + h where h is Chebyshev distance to goal. Same answer; potentially fewer expansions.

Time
O(n^2 log n^2)
Space
O(n^2)
function shortestPathAstar(grid) {
  const n = grid.length;
  if (grid[0][0] !== 0 || grid[n-1][n-1] !== 0) return -1;
  const dirs = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]];
  const heuristic = (r, c) => Math.max(n - 1 - r, n - 1 - c);
  const pq = [[1 + heuristic(0, 0), 1, 0, 0]];
  const visited = new Set();
  visited.add('0,0');
  while (pq.length) {
    pq.sort((a, b) => a[0] - b[0]);
    const [, d, r, c] = pq.shift();
    if (r === n - 1 && c === n - 1) return d;
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      const key = nr + ',' + nc;
      if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] === 0 && !visited.has(key)) {
        visited.add(key);
        pq.push([d + 1 + heuristic(nr, nc), d + 1, nr, nc]);
      }
    }
  }
  return -1;
}

Tradeoff: Same asymptotic worst-case but often faster in practice. Mention only if interviewer asks for an optimization — BFS is the expected answer.

DoorDash-specific tips

DoorDash interviewers test the BFS reflex. State 'BFS, not DFS, because we want SHORTEST path in an unweighted grid' BEFORE coding. The 8-direction array catches candidates who default to 4 — explicitly say 'including diagonals' to ground the directions.

Common mistakes

  • Using 4-directional moves instead of 8 — the diagonals count.
  • Forgetting to check grid[0][0] and grid[n-1][n-1] are 0 (early return -1).
  • Off-by-one — path LENGTH is number of cells visited, including start and end.

Follow-up questions

An interviewer at DoorDash may pivot to one of these next:

  • Shortest Bridge (LC 934) — bridge two islands with the minimum filled water.
  • Walls and Gates (LC 286) — multi-source BFS.
  • 01 Matrix (LC 542) — BFS from all 0s simultaneously.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why BFS and not DFS?

BFS expands in level-order, so the first time you reach (n-1, n-1), the distance IS the shortest. DFS could find a path but not necessarily the shortest without explicit min-tracking.

Why mutate grid?

Marks as visited without an extra Set. Saves memory. Mention out loud: 'if I can't mutate, I'll use a separate visited Set.'

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Shortest Path in Binary Matrix and other DoorDash interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →