Breadth-first search
Explore in rings of equal distance with a queue; the first time you reach a node is by a shortest path.
Shortest Path in a Grid. grid[r][c] is 0 for open and 1 for wall. Moving up, down, left or right, return the fewest steps from the top-left to the bottom-right, or -1 if impossible.
Signals that point here
- "Shortest", "minimum steps", "fewest moves" in an unweighted graph or grid.
- Level-order traversal of a tree; "nodes at distance k".
- Spreading processes: rotting oranges, walls and gates, word ladder.
The idea
A queue processes nodes in order of distance: all distance-d nodes leave before any distance-d + 1 node. So the first time the target is dequeued, its distance is minimal.
Mark a cell as seen when you enqueue it, not when you dequeue it. Otherwise the same cell enters the queue several times and the search can blow up from linear to quadratic.
from collections import deque
def shortest_path(grid: list[list[int]]) -> int:
rows, cols = len(grid), len(grid[0])
if grid[0][0] or grid[rows - 1][cols - 1]:
return -1
queue = deque([(0, 0, 0)]) # row, col, distance
seen = {(0, 0)}
while queue:
r, c, d = queue.popleft()
if (r, c) == (rows - 1, cols - 1):
return d
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and not grid[nr][nc] and (nr, nc) not in seen:
seen.add((nr, nc)) # mark on enqueue
queue.append((nr, nc, d + 1))
return -1public static class Bfs
{
public static int ShortestPath(int[][] grid)
{
int rows = grid.Length, cols = grid[0].Length;
if (grid[0][0] == 1 || grid[rows - 1][cols - 1] == 1) return -1;
var queue = new Queue<(int R, int C, int D)>();
var seen = new bool[rows, cols];
queue.Enqueue((0, 0, 0)); seen[0, 0] = true;
int[] dr = { 1, -1, 0, 0 }, dc = { 0, 0, 1, -1 };
while (queue.Count > 0)
{
var (r, c, d) = queue.Dequeue();
if (r == rows - 1 && c == cols - 1) return d;
for (int k = 0; k < 4; k++)
{
int nr = r + dr[k], nc = c + dc[k];
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || grid[nr][nc] == 1 || seen[nr, nc]) continue;
seen[nr, nc] = true; // mark on enqueue
queue.Enqueue((nr, nc, d + 1));
}
}
return -1;
}
}Complexity
O(R·C) time and space: each cell is enqueued at most once and has four neighbours.
Pitfalls interviewers watch for
- Marking seen on dequeue, which enqueues duplicates.
- Using DFS for shortest path: it finds a path, not the shortest.
- Weighted edges: BFS is wrong; use Dijkstra (a heap), or 0-1 BFS with a deque when weights are 0 or 1.
Variants worth knowing
- Multi-source BFS: enqueue every source at distance 0 (rotting oranges, distance to nearest gate).
- Level-order traversal: process the queue in batches of
len(queue). - Bidirectional BFS for word ladder: search from both ends and stop when the frontiers meet.
Test it like the interviewer will
shortest_path([[0, 0, 0], [1, 1, 0], [0, 0, 0]])returns4shortest_path([[0, 1], [1, 0]])returns-1shortest_path([[0]])returns0shortest_path([[0, 0, 1], [1, 0, 1], [1, 0, 0]])returns4- Say the cases out loud before you run them. OpenAI's published guide names test coverage as part of the bar; see Sources.
Step through it: shortest_path([[0, 0, 0, 0], [1, 1, 0, 1], [0, 0, 0, 0], [0, 1, 1, 0]])
Each step is recorded from an instrumented copy of the Python above, run when the site was built.
Practice
Written for this site to drill the lesson. Not reported interview questions.
- Return the minutes until every orange is rotten, or -1.
- Return the level-order traversal of a binary tree as a list of lists.
- Find the length of the shortest transformation sequence between two words.
Check yourself
Why is the first dequeue of the target a shortest path?
The queue releases nodes in non-decreasing distance order.
When must you mark a node as seen?
When it is enqueued.