Shortest Path in Binary Matrix
Medium · Graphs · Array · Breadth-First Search · Matrix
Problem
You are given an n x n grid of 0s and 1s. A clear path goes from the top-left cell (0, 0) to the bottom-right cell (n - 1, n - 1) so that:
- every cell on the path is 0, and
- each step moves to one of the 8 neighbors: a cell that shares a side or a corner.
The length of a clear path is the number of cells it visits, both ends included. Return the length of the shortest clear path, or -1 if there is none.
Examples
Input: grid = [[0,0,0],[1,1,0],[1,1,0]] Output: 4
(0,0) -> (0,1) -> (1,2) -> (2,2): a diagonal step from (0,1) to (1,2) gives 4 cells.
Input: grid = [[0,1],[1,1]] Output: -1
The bottom-right cell is 1, so no path can end there.
Input: grid = [[0]] Output: 1
The start is already the end: a path of one cell.
Constraints
- n == len(grid) == len(grid[i])
- 1 <= n <= 100
- grid[i][j] is 0 or 1
Approaches
- Baseline: relax distances until nothing changes — time O(n⁴), space O(n²)
Follow-up
BFS works because every step has the same cost. If a diagonal step cost more than a straight one (say 1.4 instead of 1), the fewest steps would no longer be the shortest path; you would switch to Dijkstra's algorithm, or A* with the straight-line distance to the corner as the guide.
Related problems
Start free on Cariara · Coding problems · System design studio
