That single guarantee is why BFS is the go-to for "shortest number of steps / minimum moves" problems. The queue enforces the ring order: FIFO means you finish a whole ring before touching the next.
Graph: 0–1, 0–2, 1–3, 2–3, start at 0.
| Step | Queue (front→back) | Visited | Distance found |
|---|---|---|---|
| init | [0] | {0} | 0:0 |
| pop 0 | [1, 2] | {0,1,2} | 1:1, 2:1 |
| pop 1 | [2, 3] | {0,1,2,3} | 3:2 |
| pop 2 | [3] | — | 3 already visited |
| pop 3 | [] | — | done |
| Metric | Value | Why |
|---|---|---|
| Time | O(V + E) | Each node enqueued once; each edge examined once. |
| Space | O(V) | Queue + visited set, worst case holds a full ring. |
Grid BFS template (the most common interview form) with level counting.
import java.util.*;
/** Shortest steps from (sr,sc) to any target cell in a grid. */
public int bfs(int[][] grid, int sr, int sc) {
int rows = grid.length, cols = grid[0].length;
int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}}; // 4-directional
boolean[][] seen = new boolean[rows][cols];
Queue<int[]> q = new ArrayDeque<>();
q.offer(new int[]{sr, sc});
seen[sr][sc] = true; // mark on ENQUEUE, not on pop
int steps = 0;
while (!q.isEmpty()) {
int ringSize = q.size(); // freeze the ring boundary
for (int i = 0; i < ringSize; i++) {
int[] cell = q.poll();
int r = cell[0], c = cell[1];
if (grid[r][c] == 9) return steps; // 9 = target, found it
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
&& !seen[nr][nc] && grid[nr][nc] != 1) { // 1 = wall
seen[nr][nc] = true;
q.offer(new int[]{nr, nc});
}
}
}
steps++; // one full ring done = one more step
}
return -1; // unreachable
}
remove(0): that's O(n). Use ArrayDeque.ringSize snapshot: reading q.size() inside the loop mixes rings and destroys your step count.The tell is "shortest / fewest / minimum steps" in an unweighted setting, or "spreading outward." Common disguises:
| Disguise / phrasing | What's really asked | Twist to handle |
|---|---|---|
| "Minimum moves / steps / turns to reach X" | Shortest path, unweighted | Level-counting BFS; state may be more than (r,c) |
| "Rotting oranges / spreading infection / fire" | Multi-source BFS | Seed queue with ALL sources at distance 0 |
| "Word ladder / gene mutation" | Implicit graph, BFS shortest | Neighbor = one-change; build edges on the fly |
| "Shortest path with keys / state" (e.g. LC 864) | BFS over augmented state | Node = (cell, bitmask); visited keyed on full state |
| "Nearest 0 / nearest exit / walls-and-gates" | Multi-source distance field | BFS from all targets simultaneously |
| "Knight's minimum moves on a board" | BFS on implicit move graph | 8 knight offsets as edges; possibly infinite board → bound it |
| "Bidirectional / meet in the middle" | BFS from both ends | Alternate frontiers; stop when they intersect |