Shortest Path in Binary Matrix
Shortest Path in Binary Matrix is LeetCode 1091 (Medium). You get an n x n grid of 0s and 1s. Return the length of the shortest clear path from the top-left cell (0, 0) to the bottom-right cell (n-1, n-1), or -1 if there is none.
- A clear path visits only cells that hold
0. - Consecutive cells on the path are 8-directionally adjacent: they share an edge or just a corner.
- The length of a path is the number of cells it visits, the start and the end included.
n ≤ 100, so there are at most 10,000 cells.
- n == grid.length
- n == grid[i].length
- 1 <= n <= 100
- grid[i][j] is 0 or 1
Intuition
Treat every 0 cell as a vertex joined to the open cells among its eight neighbours. Each step adds exactly one cell, so every edge costs the same, and shortest path with equal edge costs is what breadth-first search solves.
BFS takes cells off the queue in order of path length: every cell of length 1, then every cell of length 2, and so on. So the first time the target comes off the queue, no shorter path to it can exist; a shorter one would have been processed earlier.
The length stored with a cell doubles as its visited mark: a cell that already has one was reached at least as fast, so it is never queued again.
Grid, unit-cost moves, "fewest steps from A to B": that is BFS, and it is how shortest path in binary matrix leetcode problems are meant to be solved. The detail specific to this one is the move set. Diagonals count, so each cell has eight neighbours instead of the usual four. Rotting Oranges and 01 Matrix use the same wave-by-wave BFS with four directions.
Approach
Before reading on: on the 3 x 3 example below, write the length of the shortest path to every open cell by hand. In what order did you fill them in? Now decide what the answer should be for the grid [[0]], and what happens if grid[0][0] is 1.
Reject blocked endpoints
If grid[0][0] or grid[n-1][n-1] is 1, return -1 straight away. BFS never checks the cell it was seeded with, so a blocked start would otherwise slip through.
Seed the queue with the start at length 1
Set dist[0][0] = 1 and put (0, 0) in the queue. A path is measured in cells, not moves, and the start is one of them, which is why a 1 x 1 grid answers 1.
Pop, then test for the target
Take the front cell. If it is (n-1, n-1), return its length; BFS hands out cells in order of length, so nothing shorter can still be waiting.
Try all eight neighbours
Loop dr and dc over -1, 0, 1. For each neighbour that is inside the grid, holds 0 and has no length yet, set its length to the current one plus 1 and append it. Setting the length when it is queued, not when it is popped, keeps every cell in the queue at most once.
An empty queue means no path
If the loop ends without reaching the target, every cell connected to the start has a length and the target is not one of them. Return -1.
Shortest Path in Binary Matrix solution in Python | C++ | Java
Common pitfalls
Moving in four directions only
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
for dr in (-1, 0, 1):
for dc in (-1, 0, 1):Diagonal moves are allowed. On [[0, 1], [1, 0]] the only route is the diagonal, so a four-way search returns -1 where the answer is 2, and on open grids it returns paths that are too long.
Marking a cell when it is popped instead of when it is pushed
r, c = q.popleft()
if seen[r][c]: continue
seen[r][c] = True
for ...:
if grid[nr][nc] == 0 and not seen[nr][nc]:
q.append((nr, nc, d + 1))for ...:
if grid[nr][nc] == 0 and dist[nr][nc] == 0:
dist[nr][nc] = dist[r][c] + 1
q.append((nr, nc))With eight neighbours, one open cell can be pushed by up to eight cells before it is first popped. The answer stays right, but the queue swells to several times n² entries and large open grids time out.
Starting the search on a wall
if grid[n - 1][n - 1] == 1:
return -1
q = deque([(0, 0)])if grid[0][0] == 1 or grid[n - 1][n - 1] == 1:
return -1BFS never looks at the value of the cell it was seeded with, only at its neighbours. With grid[0][0] == 1 it happily expands from the wall and can return a length, while the correct answer is -1 (the fourth example).
Edge cases
Start and target are the same cell. It is popped first and matches the target test, so the answer is 1: one cell, zero moves. This is why the start is seeded with length 1, not 0.
Complexity
Shortest Path in Binary Matrix FAQ
Why is BFS the right shortest path in binary matrix solution?
Every move adds one cell, so all edges have the same cost. BFS processes cells in increasing path length, which makes the first time it pops the target the shortest possible path. Dijkstra works too, but its heap is only needed when edge costs differ.
Can the shortest path in binary matrix Python solution reuse the grid as the visited mark?
Yes. Write grid[nr][nc] = 1 when a cell is queued and carry the length in the queue as (r, c, d). That drops the separate dist grid, but it changes the caller's input, so only do it when the interviewer says the grid may be modified.
Can A* be faster for LeetCode 1091?
On large open grids, A* with the Chebyshev distance max(|dr|, |dc|) as its heuristic usually expands fewer cells. With n ≤ 100 there are at most 10,000 cells, so plain BFS is already fast and is the expected answer.