L28 · Graphs II — BFS & Shortest Path

Series: LeetCode — From Basics to Interview-Ready · Session 28 / 65 · Phase 1 · Core patterns

Why this session exists

DFS finds a path. BFS finds the shortest one. That difference is worth exactly one data structure — a queue instead of a stack — and it unlocks a whole category of problems that DFS cannot answer correctly at any level of cleverness.

The genuinely elegant idea in this session is multi-source BFS. When a problem asks "for every cell, how far is the nearest zero" or "how many minutes until every orange rots", the instinct is to run a BFS from each source and take the minimum. That is O(sources × cells) and it times out. The better answer is to push all sources into the queue before the loop starts, at distance zero. The frontier then expands from all of them simultaneously, and the first time any cell is reached, it is reached by its nearest source. One sweep, O(cells), no per-source loop.

That trick — seed the queue with everything — is the reason this session exists as its own unit. It is the difference between a solution that passes and one that does not, and it looks like nothing when you read it.

Blank-file warm-up

Five minutes, empty file, no notes. Write from memory:

from collections import deque
q = deque(sources)     — push ALL sources first
while q: ...           — level-by-level with a for-range over len(q)

Concretely: given a grid and a list of starting coordinates, write a BFS that computes the distance from the nearest start to every reachable cell.

The three things that wobble from memory: using list.pop(0) instead of deque.popleft(), marking visited on pop instead of on push, and forgetting that all sources go in before the loop begins. Any of those is today's finding.

Pattern anatomy

The shape of problem that summons BFS: uniform-cost expansion where the question is how far, how many steps, or how many rounds. The critical word is uniform. Every edge must cost the same. The moment edges carry different weights, BFS is wrong and you need Dijkstra.

The invariant is the whole reason BFS works: the queue always holds nodes in non-decreasing order of distance from the source set. Because you only ever append nodes at distance d + 1 while popping nodes at distance d, the queue never contains a node whose distance is smaller than one already popped. Therefore the first time a node is dequeued, no shorter route to it exists.

The template. Learn this exact shape:

from collections import deque
 
def bfs(adj, sources):
    dist = {s: 0 for s in sources}
    q = deque(sources)                 # ALL sources seeded at distance 0
    while q:
        node = q.popleft()
        for nxt in adj[node]:
            if nxt not in dist:        # 'not in dist' doubles as the visited check
                dist[nxt] = dist[node] + 1
                q.append(nxt)          # mark on PUSH, not on pop
    return dist

When you need explicit levels — "how many rounds until everything is done" — use the level-batching form:

def bfs_levels(adj, sources):
    seen = set(sources)
    q = deque(sources)
    level = 0
    while q:
        for _ in range(len(q)):        # snapshot the size: this is one whole level
            node = q.popleft()
            for nxt in adj[node]:
                if nxt not in seen:
                    seen.add(nxt)
                    q.append(nxt)
        level += 1                     # only after the full level drains
    return level - 1                   # levels counted, minus the initial one

for _ in range(len(q)) is the line that matters. Python evaluates len(q) once, before the loop body starts appending, so the range is fixed to the current level's size. That is what makes the batching correct.

And the grid version, which is what you will actually write in an interview:

DIRS = ((1, 0), (-1, 0), (0, 1), (0, -1))
 
def grid_bfs(grid, sources):
    R, C = len(grid), len(grid[0])
    dist = [[-1] * C for _ in range(R)]
    q = deque()
    for r, c in sources:
        dist[r][c] = 0
        q.append((r, c))
    while q:
        r, c = q.popleft()
        for dr, dc in DIRS:
            nr, nc = r + dr, c + dc
            if 0 <= nr < R and 0 <= nc < C and dist[nr][nc] == -1:
                dist[nr][nc] = dist[r][c] + 1
                q.append((nr, nc))
    return dist

The dist matrix initialised to −1 does triple duty: distance storage, visited marker, and unreachable indicator. Three responsibilities, one array, no separate set.

The cue

You are looking at a BFS problem when the statement contains one of these tells:

1. "Minimum number of steps / moves / transformations / mutations" in a setting where every step costs the same. Word Ladder, Open the Lock, Minimum Genetic Mutation. All the same problem with a different neighbour function.
2. "Nearest" or "closest" for every cell. 01 Matrix, Walls and Gates, Shortest Distance from All Buildings. This is the multi-source signal — seed every zero, every gate, every source at once.
3. "How many rounds / minutes / iterations until X spreads everywhere". Rotting Oranges, Infection spread. Level-batched BFS, and the answer is the level count.
4. "Shortest path in an unweighted graph." Said outright. If the problem says weighted, or the edges have costs, stop — that is Dijkstra, not this.
5. A state space you can enumerate with a defined transition. Lock combinations, board configurations, word transformations. The "graph" is never given; you generate neighbours from the current state on demand.

Tell 5 is the one people miss. In Word Ladder there is no adjacency list anywhere in the input. The graph is implicit: nodes are words, and two words are adjacent if they differ in exactly one letter. Recognising that a state space is a graph is the same leap as recognising that a grid is a graph.

The negative cue: if edges have different weights, BFS gives a wrong answer that looks plausible. It will find a path with the fewest edges, which is not the cheapest path. That distinction has cost people offers.

Guided solve

Rotting Oranges. A grid of 0 (empty), 1 (fresh orange), 2 (rotten orange). Every minute, any fresh orange orthogonally adjacent to a rotten one becomes rotten. Return the minutes until no fresh orange remains, or −1 if impossible.

Name the graph first. Nodes: grid cells. Edges: orthogonal adjacency. But the key observation is about time: all currently-rotten oranges rot their neighbours simultaneously. That simultaneity is exactly what a level-batched multi-source BFS models. Minute k corresponds to BFS level k.

So the shape is: seed the queue with every initially-rotten orange, count fresh oranges as you scan, then drain level by level.

from collections import deque
 
def orangesRotting(grid):
    R, C = len(grid), len(grid[0])
    q = deque()
    fresh = 0
    for r in range(R):
        for c in range(C):
            if grid[r][c] == 2:
                q.append((r, c))
            elif grid[r][c] == 1:
                fresh += 1
 
    if fresh == 0:
        return 0                        # nothing to rot: zero minutes, not -1
 
    minutes = 0
    DIRS = ((1, 0), (-1, 0), (0, 1), (0, -1))
    while q and fresh > 0:
        for _ in range(len(q)):
            r, c = q.popleft()
            for dr, dc in DIRS:
                nr, nc = r + dr, c + dc
                if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    fresh -= 1
                    q.append((nr, nc))
        minutes += 1
 
    return minutes if fresh == 0 else -1

Three decisions worth defending out loud.

Why the initial scan does two jobs. One pass collects the sources and counts the fresh oranges. The fresh counter is what lets you answer the −1 case without a second full scan at the end: if any fresh orange survives the BFS, it was unreachable from every rotten source.

Why while q and fresh > 0 rather than just while q. Without the fresh condition you drain one extra level after the last orange rots — the final rotten cells get dequeued, find no fresh neighbours, and minutes increments anyway. That off-by-one gives you an answer one higher than correct, which passes the trivial cases and fails the real ones.

Why the fresh == 0 early return. A grid with no fresh oranges at all takes zero minutes. Without the guard, if there are also no rotten oranges, the queue is empty, the loop never runs, minutes stays 0 and you return 0 anyway — that case is fine. But if there are rotten oranges and no fresh ones, you would drain one level and return 1. Wrong. The guard makes the intent explicit rather than relying on the loop condition to save you.

Trace on [[2,1,1],[1,1,0],[0,1,1]]. Sources: (0,0). Fresh: 6. Level 1 rots (0,1) and (1,0) — fresh 4. Level 2 rots (0,2) and (1,1) — fresh 2. Level 3 rots (2,1) — fresh 1. Level 4 rots (2,2) — fresh 0, loop exits. Answer 4.

Solo timed

Fifteen minutes each, timer visible, no editorial until it fires.

• 01 Matrix — for each cell, the distance to the nearest 0. Ask yourself which cells belong in the initial queue: the zeros, or the ones? Pick the wrong set and the problem becomes far harder than it is.
• Word Ladder — the graph is never given. Think about how to generate neighbours of a word cheaply; the naive "compare against every word in the list" is O(N·L) per expansion and there is a wildcard-bucket trick that beats it.

If both land early, do Open the Lock. Same state-space BFS, and the deadends set is a visited pre-seed rather than a separate check.

Common failure modes

Marking visited on pop instead of on push. If you only mark when dequeuing, the same node can be appended many times before its first pop, and the queue blows up. In dense grids this turns O(V) into something much worse and occasionally TLEs. Mark the instant you append.

Using list.pop(0) instead of deque.popleft(). pop(0) on a Python list is O(n) because every remaining element shifts left. That silently converts your O(V + E) BFS into O(V²). No wrong answer, just a timeout you cannot explain.

Incrementing the level counter inside the inner loop. The level increment belongs after the entire for _ in range(len(q)) batch drains. Inside, you count nodes rather than levels.

Recomputing len(q) inside the batch loop. Writing while i < len(q) instead of snapshotting the size means newly-appended next-level nodes get folded into the current level, and the level count collapses to 1.

Running single-source BFS in a loop for a nearest-X problem. Correct answer, wrong complexity. It passes the samples and TLEs on the large case.

Applying BFS to a weighted graph. Produces the fewest-edges path rather than the cheapest path. There is no error and the output looks reasonable, which is what makes it dangerous.

Complexity

Time: O(V + E). Each node is enqueued at most once, because the visited mark is written at push time. Each dequeue examines that node's adjacency list once, so every edge is inspected at most twice in an undirected graph. On a grid, V = m·n and each cell has at most four neighbours, giving O(m·n) — linear in cells.

Multi-source changes nothing asymptotically. Seeding k sources costs O(k) up front, and k ≤ V, so it disappears into the O(V) term. This is the key result: BFS from 10,000 sources costs the same as BFS from 1.

Space: O(V). The queue holds at most one full frontier, and the visited/distance structure holds up to V entries. On a wide grid the frontier can be O(min(m, n)) at any instant, but the distance matrix is O(m·n) regardless, so the bound stands.

For Word Ladder specifically, the neighbour generation adds a factor: with words of length L and a wildcard-bucket preprocessing pass, you get O(N·L²) overall, where the L² comes from building L wildcard patterns per word and each pattern costing O(L) to construct.

Spaced queue

Re-solve whatever is due before starting anything new today. Status ladder:

• cold — solved unaided, first attempt clean → next review in 60 days
• warm — solved but slowly or with a stumble → 21 days
• hint — needed a nudge to get started → 7 days
• failed — could not produce a working solution → 2 days, then 7 days

Rotting Oranges enters the queue today. If you wrote the level increment in the wrong place or used pop(0), that is failed even if the final submission was accepted — the queue tracks what came out of cold memory, not what came out after debugging.