BFS Pattern Recognition: Every Problem Hides One of Five Signals
- BFS applies when a problem asks for minimum steps, level-by-level output, spreading effects with time, multi-source nearest queries, or implicit graph transformations
- Mark visited on enqueue, not on dequeue; the omission bloats the queue from O(n) to O(n²) entries on dense or implicit graphs
- Multi-source BFS pre-loads all k sources at distance 0, collapsing O(k × V) separate traversals into a single O(V) pass
- Implicit graphs (Word Ladder, lock combinations) have no adjacency list; generate neighbors on the fly by applying a transformation rule to the current state
- The
for _ in range(len(queue))snapshot is the cleanest way to track BFS levels without a separate distance dictionary - BFS space is O(W) for frontier width; DFS uses O(H) for depth. Choose based on whether your graph is wide or tall.
You've seen the queue. You know how BFS works. The hard part is not the algorithm. It's recognizing that you should use it at all.
BFS problems rarely announce themselves as "graph traversal." They come dressed as oranges rotting in a grid, words transforming one letter at a time, or knights clomping across a chessboard. The graph is invisible. You have to see it.
Below is the BFS pattern recognition checklist, the template that avoids the subtle bug half the tutorials have, and the one mistake that quietly breaks every second implementation.
Five BFS Pattern Recognition Signals
If a problem asks for the minimum number of steps, moves, or transformations, BFS is almost certainly the answer. That single word "minimum" combined with discrete steps is the strongest signal there is.
1. "Minimum steps / shortest path" in an unweighted context. Knight on a chessboard, minimum moves to reach a target, fewest operations to solve a puzzle. Unweighted means every edge costs 1. BFS visits nodes in exact order of their distance from the source, so the first time you reach the target, that distance is optimal. The proof is two sentences and makes you feel smart.
2. Level-by-level processing. Binary tree level order traversal, printing nodes at each depth, finding the minimum depth of a binary tree. These are BFS by definition. The queue processes an entire level before touching the next one. This is not a clever trick. It is the fundamental property.
3. Spreading effects with a time component. Rotting oranges spreading minute by minute, fire through a grid, infection across a network. Each "minute" is one BFS level. The time when every node is first reached equals its shortest distance from any source. If the problem describes "a thing happening to neighbors each round," your BFS alarm should go off.
4. "Nearest" something with multiple sources. Distance from each cell to the nearest gate, nearest water, nearest 0. Running a separate BFS from each source costs O(k × V) when O(V) is possible. More on this in a moment.
5. Implicit graph, explicit transformation rule. Word Ladder, sliding puzzles, lock combinations. No adjacency list exists. You generate neighbors on the fly by applying a rule. The graph is too large to precompute, and BFS doesn't care.
When you see one of these in a problem statement, reach for BFS before you start writing anything else.
The Template, and the Bug in Half the Tutorials
from collections import deque def bfs(graph, start, target): queue = deque([start]) visited = {start} # mark visited ON ENQUEUE, not on dequeue while queue: node = queue.popleft() if node == target: return True for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) # here, not after popleft queue.append(neighbor) return False
Mark the node as visited the moment you enqueue it, not when you pop it. This is the most common subtle bug in BFS implementations, and it is the kind of thing that looks fine on a small test case and destroys you on a dense graph.
Suppose two nodes A and B both have C as a neighbor. If you mark C visited only on dequeue, processing A enqueues C. Processing B before C is ever popped enqueues C again. On a sparse graph you get a few harmless duplicates. On a complete graph with n nodes, every node ends up in the queue O(n) times, ballooning from O(n) to O(n²) entries. On an implicit infinite graph, it turns a manageable BFS into a queue that eats all your memory and your will to live.
The fix is mechanical: add to visited and enqueue in the same if block, in that order.
For a grid:
from collections import deque def bfs_grid(grid, start_r, start_c, target): rows, cols = len(grid), len(grid[0]) queue = deque([(start_r, start_c)]) visited = {(start_r, start_c)} directions = [(0, 1), (0, -1), (1, 0), (-1, 0)] steps = 0 while queue: for _ in range(len(queue)): # process one full level r, c = queue.popleft() if (r, c) == target: return steps for dr, dc in directions: nr, nc = r + dr, c + dc if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in visited: if grid[nr][nc] != '#': # whatever your obstacle condition is visited.add((nr, nc)) queue.append((nr, nc)) steps += 1 return -1
The for _ in range(len(queue)) inner loop is how you track levels without a separate distance dictionary. At the start of each outer iteration, snapshot the queue size. Process exactly that many nodes. They all belong to the current level. Then increment your step counter. Everything enqueued during that batch belongs to the next level.
Two alternatives: store (node, distance) tuples directly in the queue, or push a None sentinel between levels. Both work. The size-snapshot approach is cleanest because it keeps the queue homogeneous.
The visited set goes at enqueue. Every single time. No exceptions.
Multi-Source BFS: One Queue, All Sources
Rotten Oranges (LeetCode 994) trips people up not because BFS is hard, but because there are multiple starting points. The naive approach: run BFS from each rotten orange, take the maximum. That's O(k × V), and it also feels wrong the moment you type it out.
The right approach: treat all rotten oranges as a single super-source at distance 0.
from collections import deque def oranges_rotting(grid): rows, cols = len(grid), len(grid[0]) queue = deque() fresh = 0 for r in range(rows): for c in range(cols): if grid[r][c] == 2: queue.append((r, c)) # all rotten oranges at time 0 elif grid[r][c] == 1: fresh += 1 if fresh == 0: return 0 directions = [(0,1),(0,-1),(1,0),(-1,0)] minutes = 0 while queue and fresh > 0: for _ in range(len(queue)): r, c = queue.popleft() for dr, dc in directions: nr, nc = r + dr, c + dc if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1: grid[nr][nc] = 2 fresh -= 1 queue.append((nr, nc)) minutes += 1 return minutes if fresh == 0 else -1
BFS has no requirement that the queue starts with exactly one node. Pre-loading all k sources is equivalent to a virtual super-source connected to each of them at zero cost. The BFS then finds the distance from the nearest source to every reachable node automatically.
Walls and Gates (LeetCode 286), 01 Matrix (LeetCode 542), and Map of Highest Peak (LeetCode 1765) are all the same pattern. Once you see it once, you see it everywhere.
Implicit Graphs: When the Graph Lives in Your Head
Word Ladder (LeetCode 127): start word, end word, a dictionary. Change one letter at a time. Find the minimum steps. No adjacency list. You generate neighbors by trying all 26 substitutions at each position:
from collections import deque def ladder_length(beginWord, endWord, wordList): word_set = set(wordList) if endWord not in word_set: return 0 queue = deque([(beginWord, 1)]) visited = {beginWord} while queue: word, length = queue.popleft() for i in range(len(word)): for c in 'abcdefghijklmnopqrstuvwxyz': next_word = word[:i] + c + word[i+1:] if next_word == endWord: return length + 1 if next_word in word_set and next_word not in visited: visited.add(next_word) queue.append((next_word, length + 1)) return 0
The graph is implicit but the BFS logic is identical. The only difference is how you compute neighbors: instead of looking up an adjacency list, you apply a rule.
Any problem with states and valid transitions is a graph problem, even when no graph is given. Knight moves. Rubik's cube face rotations. Lock combinations. They're all graphs where nodes are states and edges are legal operations. BFS gives you the shortest sequence.
One practical note: if your state is a 2D grid or a list, convert it to a string or tuple before adding to visited. Mutable containers can't be hashed, and you will discover this at the worst possible moment.
Complexity: Two Numbers, Both Important
BFS time is O(V + E): each vertex is enqueued and dequeued once, and each edge is examined once when processing its source.
Space is O(W), where W is the maximum width of the BFS frontier. For a balanced binary tree that's O(n/2) at the last level. For a grid it's O(min(rows, cols)) at the diagonal. The queue never holds more than one complete level at a time.
DFS uses O(H) space where H is tree height. For a balanced tree: O(log n) DFS vs O(n) BFS. For a skewed tree DFS degenerates to O(n) depth while BFS stays at O(1) width. Choose based on which is smaller for your specific graph structure.
One Python trap that gets people more often than it should: never use list.pop(0) as your queue. That operation is O(n) because every element shifts left. A 10,000-node BFS with pop(0) runs 10,000x slower than the same code with deque.popleft(). Use collections.deque every time, without exception, and you never think about this again.
"What's the time complexity?" The three words that separate the people who know from the people who guess and hope.
Make the Decision Fast
The decision process for any interview problem:
- Minimum/shortest/fewest requirement? Think BFS.
- All transitions equal cost? Standard BFS. Costs 0 or 1? Use 0-1 BFS (deque with front/back push). Costs vary? Use Dijkstra.
- Explicit graph? Use the adjacency list. Grid? Use direction arrays. No graph? Define your state and write a neighbor-generation rule.
- Multiple equal-cost sources? Pre-load all of them.
- Need the level or distance? Use the size-snapshot pattern.
The visited set goes at enqueue time, the queue is a deque, and boundary checks happen before pushing. Everything else is problem-specific.
The hardest part of a BFS problem is never the traversal. It's recognizing that you have a shortest-path problem on a graph the problem statement didn't tell you was a graph. Once you see it, the code is almost mechanical.
If you want to practice recognizing these signals under pressure, SpaceComplexity runs voice-based DSA mock interviews where the interviewer probes your reasoning, not just your code.