Skip to main content

1091. Shortest Path in Binary Matrix

mediumAsked at Meta

Find the shortest path in a binary matrix from top-left to bottom-right, moving through 0-cells in 8 directions. Meta asks this to test whether you reach for BFS for shortest-path on unweighted grids.

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

Source citations

Public interview reports confirming this problem appears in Meta loops.

  • Glassdoor (2026-Q1)— Meta E4 onsite reports cite this as a recurring BFS problem.
  • Blind (2025-09)— Recurring Meta interview question.

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. 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

Approaches

1. BFS (optimal)

Start from (0,0). Expand to 8 neighbors at each step. First time we reach (n-1, n-1) is the shortest path.

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 q = [[0, 0, 1]];
  const visited = new Set();
  visited.add(0);
  while (q.length) {
    const [r, c, d] = q.shift();
    if (r === n - 1 && c === n - 1) return d;
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] === 0 && !visited.has(nr * n + nc)) {
        visited.add(nr * n + nc);
        q.push([nr, nc, d + 1]);
      }
    }
  }
  return -1;
}

Tradeoff: Standard BFS. Visited set is a flat Set keyed by row*n+col to avoid string allocation. Each cell visited at most once.

2. A* with Chebyshev heuristic (optimization)

A* search using Chebyshev distance (max of dx, dy) as the heuristic — admissible because 8-direction movement matches that distance.

Time
O(n^2 log n^2)
Space
O(n^2)
// A* outline — uses a priority queue keyed on f = g + h.
// Improves average case but same worst case as BFS.
// Mention only if interviewer asks for optimization.

Tradeoff: A* often skipped in 45-min interviews because BFS is already optimal in worst case and A* needs a priority queue. Mention as an extension if asked.

Meta-specific tips

Meta interviewers grade this on the BFS pattern. State out loud: 'For shortest path on an unweighted grid, BFS is the right tool because the first arrival at the target IS the shortest path.' Then handle two edge cases upfront: (1) start or end is blocked → -1; (2) n=1 with grid[0][0] === 0 → 1.

Common mistakes

  • Forgetting to check that start and end are 0 — otherwise BFS will never reach the goal.
  • Using DFS — works but doesn't give shortest path.
  • Iterating 4 directions instead of 8.
  • Forgetting that the path length counts cells, not edges (so length is 1 when start == end).

Follow-up questions

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

  • What if some cells had cost > 1 (weighted edges)?
  • What if you could break through K walls (LC 1293)?
  • What if the grid is huge and start/end are close? (Bidirectional BFS.)

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 explores cells in order of distance. The first time we touch the target, we've found the shortest path. DFS could find a longer path first.

8 directions, not 4 — why does this matter?

Diagonal moves let you cut corners. Forgetting them gives wrong answers on inputs where the optimal path zigzags diagonally.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →