Breadth-First Search Pattern: Template + 233 LeetCode Problems

What the breadth-first search pattern is

Breadth-first search visits every node at distance k before any node at distance k+1, and that ordering is the entire reason to prefer it: on an unweighted graph the first time BFS reaches a node is guaranteed to be by a shortest path, so the search can stop the moment the target appears. Distance is tracked either by carrying it in the queue alongside the node, or by draining the queue one full level at a time — the level form is what you want when the answer is per-level, such as a right-side view or the maximum value on each row. Mark nodes as seen when they are enqueued, not when they are dequeued, or the same node enters the queue once per incoming edge and the cost stops being linear. The multi-source variant is worth recognising on sight: seeding the queue with every starting cell at once computes the distance from the nearest source for every cell in one pass, which is how rotting oranges and nearest-zero problems avoid running a separate BFS per source.

When to use it

• —The question is the minimum number of steps, moves, or transformations.
• —The graph is unweighted — with weights, this becomes Dijkstra and needs a heap.
• —The answer is per level: a level order, a right-side view, a level sum.
• —Distance from the nearest of several sources is needed, which one multi-source pass gives you.

The breadth-first search template in Python

The shape, not a solution to any one problem. Adapt the condition and the summary being maintained; the skeleton stays the same across the 233 problems listed below.

from collections import deque

def shortest_steps(graph, start, goal):
    seen = {start}
    queue = deque([(start, 0)])

    while queue:
        node, steps = queue.popleft()
        if node == goal:
            return steps               # first arrival is the shortest one
        for neighbour in graph[node]:
            if neighbour not in seen:
                seen.add(neighbour)    # mark on ENQUEUE or the queue duplicates
                queue.append((neighbour, steps + 1))

    return -1

Complexity characteristics

Time

O(V + E)

Auxiliary space

O(V)

The same linear traversal cost as depth-first search: the difference is the order of the visits, not the amount of work. The queue holds the widest level rather than the deepest path, which on a wide graph or a filled grid is O(V) and can be considerably more memory than DFS uses on the same input. A multi-source pass costs the same single traversal however many sources are seeded, which is the whole reason to prefer it to one BFS per source.

All 233 breadth-first search LeetCode problems

Every problem in the library the breadth-first search pattern applies to, grouped by LeetCode's own difficulty rating. 185 of the 233 carry a complete Python solution with a worked example and complexity analysis; the rest are listed for completeness, with the LeetCode Premium ones marked.

Related patterns

Problems sit in more than one pattern more often than not, and the overlap is where the interesting follow-up questions live.

Breadth-First Search pattern FAQ

More ways in: all 22 patterns, the curated study lists, or the full problem list.