How do you solve Shortest Path in Binary Matrix?

Implement BFS starting from (0,0) with distance 1. Use a queue to explore all 8-directional neighbors that are within bounds, unblocked, and unvisited. Mark neighbors as visited when enqueued to avoid duplicates. Return the distance upon reaching the target cell. If the queue empties without reaching the target, return -1.

Shortest Path in Binary Matrix

Q: What is the time complexity of Shortest Path in Binary Matrix?

O(n^2). Each cell in the n x n grid is visited at most once. Each visit involves checking up to 8 neighbors, resulting in O(n^2) operations.

Q: What pattern does Shortest Path in Binary Matrix use?

The Pattern: BFS (Shortest Path on Unweighted Graph) The Heuristic: When a problem asks for the shortest path or minimum steps on a grid or graph with uniform edge weights, BFS guarantees the shortest path by exploring nodes in order of increasing distance, allowing immediate termination upon reaching the target.

Medium BFS

Problem

Given an n x n binary matrix grid, return the length of the shortest clear path from top-left to bottom-right. If no such path exists, return -1. A clear path is a sequence of cells where each adjacent pair is connected 8-directionally and all cells have value 0.

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

Example

Input: grid = [[0,0,0],[1,1,0],[1,1,0]]

Output: 4

Starting at (0,0) with distance 1, BFS expands outward layer by layer. First, it visits (0,1). Next layer includes (0,2) and (1,2). From (1,2), BFS reaches (2,2) at distance 4, which is the bottom-right target. Because BFS explores all cells at each distance before moving deeper, the first time the target is reached guarantees the shortest path length.

Approach

Straightforward Solution

A Depth-First Search (DFS) could find a path but does not guarantee shortest length and would require exploring all paths, leading to exponential time complexity.

Core Observation

The shortest path in a grid with uniform step cost is found by exploring neighbors in layers, ensuring the first time a cell is reached is via the shortest path.

Path to Optimal

Preview

Recognizing the problem as shortest path on an unweighted graph suggests BFS. BFS explores nodes in order of increasing distance from the start, so the first time the target is reached, the shortest path length is known…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Implement BFS starting from (0,0) with distance 1. Use a queue to explore all 8-directional neighbors that are within bounds, unblocked, and unvisited…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n^2)

Each cell in the n x n grid is visited at most once. Each visit involves checking up to 8 neighbors, resulting in O(n^2) operations.

Space

O(n^2)

The visited set and queue can hold up to O(n^2) cells in the worst case, which is necessary to track explored states and maintain BFS order.

Pattern Spotlight

BFS (Shortest Path on Unweighted Graph)

When a problem asks for the shortest path or minimum steps on a grid or graph with uniform edge weights, BFS guarantees the shortest path by exploring nodes in order of increasing distance, allowing immediate termination upon reaching the target.

Solution

Python

1from collections import deque
2
3class Solution:
  def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
      if grid[0][0] == 1:
          return -1
      
      def valid(row, col):
          return 0 <= row < n and 0 <= col < n and grid[row][col] == 0
      
      n = len(grid)
      seen = {(0, 0)}
      queue = deque([(0, 0, 1)]) 
      directions = [(0, 1), (1, 0), (1, 1), (-1, -1), (-1, 1), (1, -1), (0, -1), (-1, 0)]
      
      while queue:
          row, col, steps = queue.popleft()
          if (row, col) == (n - 1, n - 1):
              return steps
          
          for dx, dy in directions:
              next_row, next_col = row + dy, col + dx
              if valid(next_row, next_col) and (next_row, next_col) not in seen:
                  seen.add((next_row, next_col))
                  queue.append((next_row, next_col, steps + 1))
      
      return -1

Step-by-Step Solution

Handle Blocked Start Cell Edge Case

5if grid[0][0] == 1:
6    return -1

Objective

To immediately return -1 if the starting cell is blocked, as no path can begin.

Key Insight

If the top-left cell is blocked (value 1), no path can start, so the algorithm can terminate early without further computation. This early exit handles an important edge case efficiently.

Interview Quick-Check

State & Boundaries

Check the start cell before any processing because a blocked start means no valid path exists.

Validate Grid Coordinates and Blockage

To verify whether a candidate neighbor cell is inside the grid boundaries and unblocked before BFS explores it.

Initialize BFS State and Movement Directions

To set up the grid size, visited set, BFS queue with starting position and distance, and all 8 possible movement directions.

Explore Neighbors Layer-by-Layer to Find Shortest Path

To perform BFS by dequeuing cells, checking for the target, and enqueueing valid, unvisited neighbors with incremented distance.

Return -1 When No Path Exists

To return -1 if BFS completes without reaching the target, indicating no valid path exists.

4 more steps with full analysis available on Pro.

Line Analysis

This solution has 6 Critical lines interviewers watch for.

Line 18 Critical

if (row, col) == (n - 1, n - 1):

Check if the current cell is the target cell.

Identifying the target cell allows immediate termination with the shortest path length, leveraging BFS's layer order.

Line 5 Critical

if grid[0][0] == 1:

Check if the starting cell is blocked.

If the start cell is blocked, no path can begin, so the algorithm must terminate immediately to avoid unnecessary computation.

Line 13 Critical

queue = deque([(0, 0, 1)])

Initialize the BFS queue with the starting cell and initial distance 1.

Starting BFS with the start cell at distance 1 sets the baseline for path length counting and exploration order.

Full line-by-line criticality + rationale for all 18 lines available on Pro.

Test Your Understanding

Why does BFS guarantee that the first time the target cell is reached, the shortest path length has been found?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Shortest Path in Binary Matrix from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Shortest Path in Binary Matrix drill

or drill a free problem

1	`from collections import deque`
2
3	`class Solution:`
4	`def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:`
5	`if grid[0][0] == 1:`
6	`return -1`
7
8	`def valid(row, col):`
9	`return 0 <= row < n and 0 <= col < n and grid[row][col] == 0`
10
11	`n = len(grid)`
12	`seen = {(0, 0)}`
13	`queue = deque([(0, 0, 1)])`
14	`directions = [(0, 1), (1, 0), (1, 1), (-1, -1), (-1, 1), (1, -1), (0, -1), (-1, 0)]`
15
16	`while queue:`
17	`row, col, steps = queue.popleft()`
18	`if (row, col) == (n - 1, n - 1):`
19	`return steps`
20
21	`for dx, dy in directions:`
22	`next_row, next_col = row + dy, col + dx`
23	`if valid(next_row, next_col) and (next_row, next_col) not in seen:`
24	`seen.add((next_row, next_col))`
25	`queue.append((next_row, next_col, steps + 1))`
26
27	`return -1`