Shortest Path in Binary Matrix
Medium · Graphs · Explanation and code example
Bidirectional Breadth First Search
How it works
Standard BFS explores outward from the source in all directions. Bidirectional BFS runs two searches simultaneously: one from the start and one from the end. When the two search frontiers meet, we have found the shortest path. This reduces the search space significantly because instead of exploring a circle of radius d, we explore two circles of radius d/2. The total area explored is roughly half of what single-direction BFS would cover.
Steps
- Handle edge cases: if start or end is blocked, return
-1. If the grid is1x1, return1. - Initialize two queues:
q1starting from(0, 0)andq2starting from(N-1, N-1). - Mark the start cell with
-1and the end cell with-2to distinguish the two frontiers. - Alternate between expanding
q1andq2:- For each cell in the current queue, explore all 8 neighbors.
- If a neighbor belongs to the other frontier (
endorstart), return the current path length. - If a neighbor is unvisited (
0), mark it with the current frontier's marker and add it to the queue.
- Swap the queues and markers after each level, incrementing the path length.
- Return
-1if the frontiers never meet.
Complexity
- Time complexity:
O(n ^ 2) - Space complexity:
O(n ^ 2)
Things to watch for
Forgetting to Check Start and End Cells
Before starting BFS, verify that both the starting cell (0, 0) and the destination cell (n-1, n-1) are passable (value 0). If either is blocked (value 1), return -1 immediately. Missing this check causes BFS to run unnecessarily or return incorrect results.
Using Only 4 Directions Instead of 8
This problem allows diagonal movement, so all 8 directions must be explored: up, down, left, right, and the four diagonals. Using only the standard 4-directional movement leads to longer paths or failure to find a path that exists through diagonal moves.
Marking Cells as Visited Too Late
Cells must be marked as visited when they are added to the queue, not when they are dequeued. Marking upon dequeue allows the same cell to be added multiple times from different neighbors, causing incorrect path lengths and memory issues. Always mark visited immediately upon enqueueing.
Python code example
from collections import deque
class Solution:
def shortestPathBinaryMatrix(self, grid: list[list[int]]) -> int:
N = len(grid)
if grid[0][0] or grid[N - 1][N - 1]:
return -1
if N == 1:
return 1
direct = [0, 1, 0, -1, 0, 1, 1, -1, -1, 1]
q1 = deque([(0, 0)])
q2 = deque([(N - 1, N - 1)])
grid[0][0] = -1
grid[N - 1][N - 1] = -2
res = 2
start, end = -1, -2
while q1 and q2:
for _ in range(len(q1)):
r, c = q1.popleft()
for d in range(9):
nr, nc = r + direct[d], c + direct[d + 1]
if 0 <= nr < N and 0 <= nc < N:
if grid[nr][nc] == end:
return res
if grid[nr][nc] == 0:
grid[nr][nc] = start
q1.append((nr, nc))
q1, q2 = q2, q1
start, end = end, start
res += 1
return -1
C++ code example
class Solution {
public:
int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
int N = grid.size();
if (grid[0][0] || grid[N - 1][N - 1]) return -1;
if (N == 1) return 1;
int direct[10] = {0, 1, 0, -1, 0, 1, 1, -1, -1, 1};
queue<pair<int, int>> q1, q2;
q1.push({0, 0});
q2.push({N - 1, N - 1});
grid[0][0] = -1;
grid[N - 1][N - 1] = -2;
int res = 2, start = -1, end = -2;
while (!q1.empty() && !q2.empty()) {
for (int i = q1.size(); i > 0; i--) {
auto [r, c] = q1.front();
q1.pop();
for (int d = 0; d < 9; d++) {
int nr = r + direct[d], nc = c + direct[d + 1];
if (nr >= 0 && nc >= 0 && nr < N && nc < N) {
if (grid[nr][nc] == end) return res;
if (grid[nr][nc] == 0) {
grid[nr][nc] = start;
q1.push({nr, nc});
}
}
}
}
swap(q1, q2);
swap(start, end);
res++;
}
return -1;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.