Multi-source BFS

“For every cell, how far is the nearest zero?” invites a BFS from each cell, which is $O((mn)^2)$ and hopeless. Reverse the question and it collapses:

Instead of searching from each cell to the nearest source, push every source into the queue at once and let one BFS expand outward from all of them simultaneously.

The first time any wave reaches a cell, it arrived from the nearest source — because BFS expands in non-decreasing distance order and all sources started at distance 0. One pass, $O(mn)$, no repeated work.

This is one of those patterns that feels like a trick the first time and obvious forever after.

What you’ll learn

• Why seeding many sources still yields correct shortest distances.
• The level loop that converts BFS layers into elapsed time or distance.
• The two ways to track visited cells — and the “distance array doubles as visited” idiom.
• How to detect unreachable cells, which is what most of these problems actually test.
• Three real LeetCode problems solved in the browser: 994, 542, 1162.

Visual intuition

Multi-source BFS is one BFS with several starting points seeded at once — not one search per source. Watch every rotten orange enter the queue before the loop begins:

gridEvery source seeds the queue, and the answer is a level countLC 994 · O(rows x cols)

×🍊🍊🍊🍊🍊🍊🍊🍊

rotten front

0,0

minute0fresh left8

1def oranges_rotting(grid):2    q = deque()3    fresh = 04    for r, row in enumerate(grid):5        for c, v in enumerate(row):6            if v == 2: q.append((r, c))     # EVERY rotten one seeds the queue7            elif v == 1: fresh += 18    minutes = 09    while q and fresh:10        for _ in range(len(q)):             # one whole minute per level11            r, c = q.popleft()12            for dr, dc in DIRS:13                if grid[nr][nc] == 1:14                    grid[nr][nc] = 2; fresh -= 1; q.append((nr, nc))15        minutes += 116    return -1 if fresh else minutes

sources1fresh8

setup1 orange is already rotten, and **all of them** seed the queue at once. That is the multi-source trick: several starting points in one BFS, which spreads from all of them simultaneously rather than needing one search per source.

Play‹›1/8⟲

Processing the queue one level at a time is what makes the answer a number of minutes rather than a number of oranges — the same level-snapshot trick as tree BFS. And note the final check for unreachable fresh oranges, which is the part most submissions miss.

The cue

You are looking at multi-source BFS when…

• “Nearest / closest” something, asked for every cell — 542, 1162.
• A process spreads simultaneously from several starting points — 994 rotting oranges, 2101 bombs.
• “Minimum time for everything to be affected” — 994, 286.
• You are about to write a loop that runs BFS once per source. That is the signal to invert it.
• “Maximise the distance from the nearest X” — 1162, which is a multi-source BFS whose answer is the last level reached.

The anti-cue: a single start and a single goal is plain BFS. Weighted edges are Dijkstra. Multi-source BFS needs uniform edge cost.

Why seeding all sources at once is correct

Think of it as adding one virtual super-source connected to every real source by a zero-cost edge. BFS from that super-source visits cells in non-decreasing distance order, and the distance it assigns to a cell is $\min_{s \in \text{sources}} \text{dist}(s, \text{cell})$ — exactly the “nearest source” answer.

Concretely: all sources enter the queue at distance 0, so the queue is correctly ordered from the outset. BFS’s invariant — that the queue holds cells in non-decreasing distance — is preserved, so the first visit to any cell is its shortest distance. Nothing about BFS changes; only the seeding does.

Template 1 — distance to the nearest source

The distance array doubles as the visited marker, which removes a whole category of bugs.

multi_source_distance.py

from collections import deque
 
 
def nearest_source_distance(grid, is_source):
    rows, cols = len(grid), len(grid[0])
    dist = [[-1] * cols for _ in range(rows)]     # -1 means "not yet reached"
    queue = deque()
 
    for r in range(rows):                        # SEED every source at once
        for c in range(cols):
            if is_source(grid[r][c]):
                dist[r][c] = 0
                queue.append((r, c))
 
    while queue:
        r, c = queue.popleft()
        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 dist[nr][nc] == -1:
                dist[nr][nc] = dist[r][c] + 1    # set distance = mark visited
                queue.append((nr, nc))
 
    return dist

Mark visited when you ENQUEUE, not when you dequeue

dist[nr][nc] = ... happens at push time. If you instead marked cells when popping them, the same cell could be enqueued by several neighbours before being processed — and with many sources that happens constantly. The queue bloats toward $O(mn)$ duplicates and cells can get a distance from a later wave.

Setting the distance as the visited mark makes it structurally impossible to enqueue a cell twice. This is the single most important habit in BFS, and it matters more here than in single-source BFS.

Template 2 — elapsed time, via level loops

When the answer is “how many minutes/steps”, process the queue one level at a time, exactly as in Tree BFS.

multi_source_levels.py

steps = 0
while queue and still_work_remaining:
    steps += 1
    for _ in range(len(queue)):          # snapshot: exactly this level
        r, c = queue.popleft()
        # ... expand neighbours, appending to the same queue

The for _ in range(len(queue)) snapshot is what separates one time step from the next. Without it every cell would be its own “minute”.

Detecting unreachable cells

This is what most of these problems really test. After the BFS finishes, any cell still holding the initial sentinel was never reached:

• 994 Rotting Oranges — a fresh orange remains: return -1.
• 542 01 Matrix — guaranteed at least one zero, so everything is reachable.
• 1162 As Far from Land as Possible — all-water or all-land: return -1.

Rather than rescanning the grid at the end, it is usually cleaner to keep a counter of the remaining work (fresh in LC 994) and decrement it as you convert cells. Then fresh == 0 is an $O(1)$ check instead of an $O(mn)$ sweep — and it also lets you stop the loop early.

Complexity

Approach	Time	Space
Multi-source BFS	$O(m \cdot n)$	$O(m \cdot n)$
BFS once per source, keeping the minimum	$O((m \cdot n)^2)$	$O(m \cdot n)$
Dijkstra from a virtual super-source	$O(mn \log mn)$	$O(m \cdot n)$

Every cell is enqueued at most once — that is what marking on enqueue buys — so the queue does $O(mn)$ pops and each pop looks at 4 neighbours. The number of sources does not appear in the bound at all: seeding 1 cell and seeding 10,000 cells cost the same, because the total work is one pass over the grid either way.

That is the whole argument for the pattern. With $k$ sources the naive approach is $k$ independent BFS runs, so on a $100 \times 100$ grid where half the cells are sources it is 5,000 traversals of 10,000 cells — $5 \times 10^7$ against $10^4$.

The super-source framing

Multi-source BFS is single-source BFS on a graph with one extra node joined to every source by a zero-weight edge. You never build that node — seeding the queue is the same thing — but the framing is the answer to “why is taking the minimum over sources correct?” It is one BFS on one graph, so the usual proof applies unchanged.

Dry run

LC 542, grid = [[0,0,0],[0,1,0],[1,1,1]]. Four zeros seed the queue at once, so the first wave already comes from four different directions.

Seed: dist is 0 at (0,0), (0,1), (0,2), (1,0), (1,2); -1 elsewhere. Queue holds those five cells.

wave	cells reached	set to	why
1	(1,1), (2,0), (2,2)	1	(1,1) is reached by whichever of its four zero-neighbours pops first — it does not matter which, they are all at distance 0
2	(2,1)	2	its only unvisited-at-wave-1 neighbours were (2,0) and (2,2), both at distance 1

Final dist:

text

0 0 0
0 1 0
1 2 1

Three things the trace shows that the code hides:

• (1,1) is contended and it does not matter. Four cells at distance 0 all want to claim it. Whichever pops first writes 1, and the dist[nr][nc] == -1 guard makes the other three no-ops. This is why marking on enqueue matters more here than in single-source BFS: with many sources, contention is the normal case, not an edge case.
• The queue never holds a cell twice, so it never exceeds $O(mn)$. Marking on dequeue instead would let (1,1) sit in the queue four times, and on a grid that is mostly sources the queue degenerates toward $4mn$ entries.
• Wave number = distance. The waves are only visible if you use the level loop; Template 1 gets the same numbers without it, because dist[r][c] + 1 carries the level in the data instead of the control flow.

LC 994, grid = [[2,1,1],[1,1,0],[0,1,1]], with the fresh counter — the same walk read as elapsed time:

minute	rots	fresh left
1	(1,0), (0,1)	4
2	(1,1), (0,2)	2
3	(2,1)	1
4	(2,2)	0

Answer 4. Note the loop condition while queue and fresh: at minute 4 the last orange rots and fresh hits 0, so the loop stops without a fifth iteration. Drop the and fresh and the count becomes 5 — the classic off-by-one in this problem, caused by counting a minute in which nothing changed.

The variant map

Variant	Sources	Answer read from	Canonical problem
Time for full spread	All rotten cells	The level count, plus a reachability check	994 Rotting Oranges
Distance to nearest source	All zeros	The whole dist grid	542 01 Matrix
Maximise distance from sources	All land cells	The last level reached	1162
Fill from all gates	All gates	The dist grid	286 (Premium)
Single source, 8 directions	One cell	Level count	1091
Spread with obstacles	All sources	Same, skipping walls	286 · 2101

Practice — real LeetCode problems

LC 994 — Rotting Oranges · Medium

Problem. In a grid, 0 is empty, 1 is a fresh orange, 2 is rotten. Each minute, every fresh orange 4-directionally adjacent to a rotten one becomes rotten. Return the minimum minutes until no fresh orange remains, or -1 if that is impossible.

Constraints. 1 <= m, n <= 10, cells are 0, 1 or 2.

Examples. [[2,1,1],[1,1,0],[0,1,1]] gives 4 · [[2,1,1],[0,1,1],[1,0,1]] gives -1 (the bottom-left 1 is isolated) · [[0,2]] gives 0

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

All rotten oranges start rotting simultaneously, which is precisely multi-source BFS. Each BFS level is one minute.

Time $O(m \cdot n)$. Space $O(m \cdot n)$ for the queue.

Three details, each with a test case:

• fresh == 0 up front returns 0. [[0,2]] and [[0]] both have nothing to rot. Without this guard the level loop never runs, minutes stays 0, and you happen to get the right answer — but the explicit guard is what makes [[0]] (no rotten oranges either) obviously correct rather than accidentally so.
• while queue and fresh. Stopping as soon as fresh hits 0 avoids counting a final, wasted minute in which nothing rots. Using just while queue would over-count by one on some grids, because the last level enqueued has no fresh neighbours left to convert.
• -1 when fresh oranges survive. [[1]] has a fresh orange and no rotten one, so it is immediately impossible.

The fresh counter is doing real work here: it gives an $O(1)$ termination test and an $O(1)$ reachability check, replacing a final $O(mn)$ rescan.

Follow-ups you should expect: “Which orange rots last?” — record the cell when you set the final level. “8-directional spread?” — extend the direction list. “Oranges rot at different rates?” — edges are no longer uniform, so it becomes Dijkstra. “Why not DFS?” — DFS does not visit in distance order, so levels would be meaningless.

LC 542 — 01 Matrix · Medium

Problem. Given an m x n binary matrix, return a matrix of the same shape where each entry is the distance to the nearest 0, measured in 4-directional steps.

Constraints. 1 <= m, n <= 10^4, m * n <= 10^4, and there is at least one 0.

Examples. [[0,0,0],[0,1,0],[0,0,0]] gives itself unchanged · [[0,0,0],[0,1,0],[1,1,1]] gives [[0,0,0],[0,1,0],[1,2,1]]

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Reverse the question. Rather than asking each 1 to find its nearest 0, start from all the zeros and let the wave assign distances as it spreads.

Time $O(m \cdot n)$. Space $O(m \cdot n)$.

The elegant part is that dist initialised to -1 serves as both the answer and the visited set. One array, two jobs, and no way to enqueue a cell twice.

Writing distances into mat in place is possible but fiddly, since 0 and 1 are meaningful input values and you would need a sentinel that cannot collide. A separate dist grid is clearer and the space is $O(mn)$ either way.

There is a neat two-pass DP alternative

This problem also yields to dynamic programming: sweep top-left to bottom-right taking min(up, left) + 1, then bottom-right to top-left taking min(down, right) + 1. Two passes, $O(mn)$ time, $O(1)$ extra space beyond the output.

It works because a shortest 4-directional path decomposes into moves that are each either “toward the top-left” or “toward the bottom-right”, so two directional sweeps capture every path. Worth mentioning — it shows you see the problem from more than one angle, and it beats BFS on space.

Follow-ups you should expect: “What if there were no zeros?” — the constraints guarantee one; otherwise every cell stays -1 and you would define the answer. “Diagonal distance?” — add the diagonal offsets, giving Chebyshev distance. “Do it with $O(1)$ extra space?” — the two-pass DP. “Nearest 0 by Manhattan distance ignoring walls?” — no traversal needed, just coordinate arithmetic.

LC 1162 — As Far from Land as Possible · Medium

Problem. Given an n x n grid of 0 (water) and 1 (land), find the water cell whose distance to the nearest land cell is maximised, and return that distance (Manhattan / 4-directional). If no water or no land exists, return -1.

Constraints. 1 <= n <= 100, cells are 0 or 1.

Examples. [[1,0,1],[0,0,0],[1,0,1]] gives 2 (the centre) · [[1,0,0],[0,0,0],[0,0,0]] gives 4 (the far corner) · [[0,0],[0,0]] gives -1

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Maximising the distance to the nearest land sounds like an optimisation over water cells, but multi-source BFS answers it directly: seed all land, expand, and the last level reached is the farthest any water cell can be.

Time $O(n^2)$. Space $O(n^2)$.

Two details worth getting right:

• Initialise dist = -1. The first iteration of the loop processes the land cells themselves and increments dist to 0, correctly recording that land is at distance 0 from land. Starting at 0 over-counts by one.
• Both degenerate cases return -1. not queue catches all-water; len(queue) == n * n catches all-land. Checking only one of them fails half the edge tests, and [[0,0],[0,0]] / [[1,1],[1,1]] cover both.

Note this is the mirror of LC 542. There the answer was the whole distance grid; here it is a single number, the maximum — which BFS hands you for free as the final level, with no need to store distances at all.

Follow-ups you should expect: “Which cell is farthest?” — record a cell when you enter the final level. “Chebyshev distance instead of Manhattan?” — use 8 directions. “Multiple such cells?” — collect all cells in the last level. “Do it without BFS?” — the two-pass DP from LC 542 computes the distance grid, then take its maximum.

LeetCode problem set

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

The one-line diagnostic

If you catch yourself writing:

python

for each source:
    bfs(source)          # <-- stop

invert it. Push every source into one queue and run a single BFS. That one change is the difference between $O((mn)^2)$ and $O(mn)$, and it applies well beyond grids — any “nearest member of a set” question on an unweighted graph takes the same shape.

5 problems

0 easy5 medium0 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

• ○994Rotting OrangesmediumLevels are minutes; a `fresh` counter gives $O(1)$ termination and reachabilityNeetCode 150amazonmicrosoftbytedance
• ○286Walls and GatespremiummediumSeed all gates, skip walls -- the canonical statement of this patternNeetCode 150
• ○54201 MatrixmediumThe `dist` grid doubles as the visited set; a two-pass DP also works
• ○1091Shortest Path in Binary MatrixmediumSingle source, but 8 directions -- plain BFS
• ○1162As Far from Land as PossiblemediumThe answer is the **last** level; guard all-land *and* all-water

Interview follow-ups

They ask	What they’re checking	The answer
“Why is seeding all sources correct?”	Whether you understand BFS’s invariant	It is BFS from a virtual super-source joined to every source by a 0-cost edge; the queue stays ordered by distance, so first visit is shortest
“Why mark visited on enqueue?”	The critical habit	Otherwise several neighbours enqueue the same cell before it is processed, bloating the queue and risking a later, larger distance
“How do you know when it is impossible?”	Rigour	Keep a counter of remaining work; a non-zero counter afterwards means unreachable cells
“Why not DFS?”	Deliberate choice	DFS does not visit in distance order, so levels and shortest distances are meaningless
“What if edges had different costs?”	The boundary	Multi-source BFS needs uniform cost; otherwise use Dijkstra with all sources pushed at distance 0
“Can you do LC 542 in $O(1)$ space?”	Breadth	Yes — the two-pass DP sweeping top-left then bottom-right
“Why dist = -1 initially in 1162?”	Attention to off-by-one	The first level processed is the land itself, which must register as distance 0

Edge-case checklist

• No sources at all — LC 994 with only fresh oranges gives -1; LC 1162 with no land gives -1.
• No targets at all — LC 994 with no fresh oranges gives 0; LC 1162 with no water gives -1. Both degenerate cases need guards.
• Everything is a source — the queue starts full and no level ever expands.
• Unreachable cells — an isolated fresh orange behind empty cells; the reason for the counter check.
• 1×1 grid — every variant must survive it.
• Off-by-one in the level counter — initialise -1 when the source level counts as distance 0, and 0 when counting elapsed steps.
• One wasted final minute (LC 994) — while queue and fresh rather than while queue.
• Duplicate enqueues — guaranteed if you mark on dequeue instead of enqueue.

Self-check

pch.quizTag Multi-source BFS — self-check

1. Why is seeding every source into one queue correct, rather than an approximation?

   A Because BFS is greedy B Because it is single-source BFS on the same graph plus a virtual super-source joined to every source at distance 0 — so the standard first-visit-is-shortest argument applies unchanged C Because all sources are at distance 0 from each other D It is only correct when the sources are adjacent
   pch.quizShowAnswer

   B — Because it is single-source BFS on the same graph plus a virtual super-source joined to every source at distance 0 — so the standard first-visit-is-shortest argument applies unchanged — The super-source is never built — seeding the queue is the same thing — but naming it is the cleanest justification, and it also explains why the source count does not appear in the complexity.

2. How does the running time depend on the number of sources k?

   A O(k · mn) B It does not — every cell is enqueued at most once, so the total is O(mn) whether there is 1 source or 10,000 C O(mn log k) D O(k²)
   pch.quizShowAnswer

   B — It does not — every cell is enqueued at most once, so the total is O(mn) whether there is 1 source or 10,000 — This is the whole point of the pattern. BFS-per-source is O(k·mn), which on a grid that is half sources is thousands of full traversals instead of one.

3. You mark cells visited when you dequeue them instead of when you enqueue them. What happens?

   A Nothing, both are correct B The same cell gets enqueued by several sources or neighbours before being processed, so the queue bloats toward O(mn) duplicates and a cell can take its distance from a later wave C The BFS returns distances one too large D It becomes a DFS
   pch.quizShowAnswer

   B — The same cell gets enqueued by several sources or neighbours before being processed, so the queue bloats toward O(mn) duplicates and a cell can take its distance from a later wave — With one source this is a mild inefficiency; with many sources contention is the normal case. In the dry run above, cell (1,1) is wanted by four zero-cells at once.

4. In LC 994 the loop is `while queue and fresh`. Why is the `and fresh` clause there?

   A To avoid an infinite loop B Because without it the last wave — which rots the final orange and then finds nothing more to do — still increments the minute counter, giving an answer one too large C To detect unreachable oranges D It is only a performance optimisation
   pch.quizShowAnswer

   B — Because without it the last wave — which rots the final orange and then finds nothing more to do — still increments the minute counter, giving an answer one too large — The dry run ends at minute 4 with fresh == 0. Looping again would count a fifth minute in which nothing changed. Tracking remaining work as a counter also makes the unreachable check O(1) instead of a final O(mn) sweep.

5. The grid gains per-cell traversal costs of 1 or 3. Does multi-source BFS still work?

   A Yes, unchanged B No — BFS requires uniform edge cost. Push every source at distance 0 into a heap and run Dijkstra instead (or a deque, if the costs are only 0 and 1) C Yes, if you sort the sources first D Yes, after multiplying all costs by their minimum
   pch.quizShowAnswer

   B — No — BFS requires uniform edge cost. Push every source at distance 0 into a heap and run Dijkstra instead (or a deque, if the costs are only 0 and 1) — The multi-source *idea* survives every weighting — seed all sources at 0 — but the structure has to match the weights: queue for uniform, deque for 0/1, heap for arbitrary.

Recall card

• Cue — “distance to the nearest X” or “time for X to spread everywhere”, with many starting cells. If you are about to write “BFS from each source”, stop.
• Do — push all sources into the queue with distance 0, then run one ordinary BFS.
• Why it is correct — identical to BFS from a virtual super-source joined to every source by a 0-cost edge.
• Mark on enqueue, never on dequeue. dist[r][c] = -1 doubles as the visited set.
• Elapsed time — level loop with a for _ in range(len(queue)) snapshot.
• Unreachable — keep a counter of remaining work; fresh > 0 at the end means -1. Loop while queue and fresh to avoid counting a dead final minute.
• Cost — $O(mn)$ time and space, independent of the source count. Weighted variants: deque for 0/1 costs, heap for arbitrary.

Recap

• Seed the queue with every source and run one BFS. Correct because it is BFS from a virtual super-source, so the first visit to a cell is its shortest distance.
• Turns $O((mn)^2)$ into $O(mn)$. If you are about to loop “BFS per source”, invert it.
• Mark visited on enqueue, never on dequeue — with many sources, duplicate enqueues are otherwise guaranteed.
• A distance array initialised to -1 is both the answer and the visited set.
• For elapsed time, process one level per step with a len(queue) snapshot.
• Track remaining work with a counter for $O(1)$ termination and unreachability checks.
• Requires uniform edge cost; weighted versions are Dijkstra (with all sources pushed at distance 0).

Next: Union-Find Problem Patterns — the other way to answer connectivity questions, and the one that handles edges arriving over time.