Community Problem
Shortest Path in Binary Matrix
Difficulty: Medium
BFS through 0-cells in 8 directions to find the shortest path from top-left to bottom-right.
Shortest Path in Binary Matrix
BFS through 0-cells in 8 directions to find the shortest path from top-left to bottom-right.
By @nehanasser
May 1, 2026
·
Updated May 18, 2026
1,188 views
6
4.2 (13)
I had this on a Lyft onsite and the gotcha was the 8-directional move set; most candidates default to 4-direction grid BFS and silently undercount paths. The catalog covers BFS and Matrix Algorithms, but it skipped this 8-direction variant which is the textbook "why is BFS the right tool for unweighted shortest path?" question.
Shortest Path in Binary Matrix
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 (0, 0) to the bottom-right cell (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 (i.e. they differ by at most 1 in row and column).
The length of a clear path is the number of visited cells of this path.
Examples
Example 1:
- Input:
grid = [[0, 1], [1, 0]] - Output:
2 - Explanation: Go diagonally from
(0, 0)to(1, 1). Two cells visited.
Example 2:
- Input:
grid = [[0, 0, 0], [1, 1, 0], [1, 1, 0]] - Output:
4 - Explanation: One shortest path is
(0,0) -> (0,1) -> (1,2) -> (2,2), four cells in total. The diagonal hop from(0,1)to(1,2)is allowed because the move is 8-directional.
Example 3:
- Input:
grid = [[1, 0, 0], [1, 1, 0], [1, 1, 0]] - Output:
-1 - Explanation: The starting cell
(0, 0)is1. No clear path exists.
Example 4:
- Input:
grid = [[0]] - Output:
1 - Explanation: Single-cell grid: the only path is one step.
Constraints
n == grid.length.n == grid[i].length.1 <= n <= 100.grid[i][j]is0or1.
Follow-up
Why BFS? On an unweighted graph (every move costs 1), BFS yields shortest paths because cells are dequeued in order of their distance from the source. Dijkstra would also work but is overkill for unit-weight edges; A* with the Chebyshev-distance heuristic is even faster in practice.
Solution
Hints
Solution Walkthrough
Approach: BFS With 8-Directional Moves (O(n^2) time, O(n^2) space)
This is unweighted shortest path on a grid graph, which BFS solves directly. The only subtlety beyond a standard 4-direction grid BFS is the move set: 8 neighbors per cell, all combinations of (dr, dc) in {-1, 0, 1}^2 except (0, 0).
Algorithm
- Reject up front if
grid[0][0] != 0orgrid[n-1][n-1] != 0. Special-casen == 1(single cell, return 1). - BFS from
(0, 0)with an explicit 8-direction list. - Track
visitedseparately (or mutate the grid to mark visited). - Return the BFS distance when the target is dequeued; return
-1if BFS exhausts.
Why It Works
BFS over an unweighted graph dequeues cells in order of their distance from the source. The first time the target is dequeued, that distance is the shortest path length. The 8-direction move set just means each cell has up to 8 neighbors instead of 4; the BFS argument is identical.
Complexity
Sample
Grid (3x3):
0 0 0
1 1 0
1 1 0
BFS from (0,0):
dist 1: (0,0)
dist 2: (0,1)
dist 3: (0,2), (1,2)
dist 4: (2,2)
Return 4.Metric Value
Time O(n^2) since each cell is enqueued at most once
Space O(n^2) for the visited grid and the BFS frontierPitfalls
- Using 4-direction moves. The problem specifies 8-direction adjacency. A 4-direction BFS would either return a longer path or
-1when a diagonal path exists. - Forgetting to check the start cell. If
grid[0][0] == 1, no path exists. Return-1early; do not enqueue. - Off-by-one on path LENGTH. The problem counts CELLS, not edges. The starting cell counts as 1, so a single-cell grid returns 1 (not 0).
Solution Code