Tap fresh oranges to rot them, then hit Spread and watch the infection wave.

Every minute, each rotten orange infects its fresh neighbors (up, down, left, right). The question: how many minutes until every orange is rotten?

This is Rotting Oranges (LC 994), and it looks straightforward until you place more than one rotten orange. With a single source, it is just BFS from one cell -- the wavefront expands outward and you count the levels. But with multiple sources, the waves overlap. Rotten orange A and rotten orange B are both spreading simultaneously, and their infection fronts collide somewhere in the middle.

Try placing 1 source, then reset and place 3. Notice how multiple sources spread simultaneously -- the infection fronts merge into a single expanding wave. Your instinct might be to run BFS from each source separately and combine the results. That instinct is wrong, and the next few screens will show you exactly why.

Here is the naive approach that almost everyone tries first: run BFS from each rotten orange separately, compute each orange's distance to every cell, then take the minimum distance across all sources.

It sounds correct. And it is correct -- it produces the right answer. But the cost is devastating. If you have k rotten oranges on a grid with n cells, you run k full BFS traversals, each visiting up to n cells. That is O(k * n) work. On a 100x100 grid with 50 rotten oranges, that is 50 million operations instead of the 10,000 that a single traversal would need.

Worse, the per-source approach re-visits cells that have already been reached by a closer source. Imagine two rotten oranges on opposite sides of the grid. Each one's BFS sweeps the entire grid, even though each cell only cares about the nearest source. All that redundant exploration is pure waste.

The next screen lets you see this waste in action. Watch the redundant-visits counter climb.

Watch BFS run from each source separately. Each rotten orange launches its own independent wavefront, and each wavefront explores the entire reachable grid -- even cells that a previous wavefront already claimed.

Pay attention to the redundant-visits counter. Every time a cell gets explored by a second (or third) BFS when it was already reached by an earlier one, that is wasted work. The counter climbs fastest in the middle of the grid, where all the wavefronts overlap. On a grid with many sources, the overlap region can be enormous.

Notice something else: the per-source approach does not even save you from computing the final answer. After all k traversals finish, you still need to scan every cell and take the minimum distance across all sources. You paid O(k * n) for the traversals, then O(k * n) more for the min-reduction. The algorithm is correct but wildly inefficient.

Same grid. Same three sources. But this time, all three start in the queue simultaneously -- at distance 0, side by side, before BFS even begins processing.

What happens? BFS dequeues the first source, enqueues its fresh neighbors at distance 1. Dequeues the second source, enqueues its fresh neighbors at distance 1. Dequeues the third source, same thing. Now all the distance-1 cells are in the queue, and BFS processes them in the usual wavefront order. The key: if two sources both neighbor the same fresh cell, the first one to reach it marks it visited. The second source skips it. No duplicates, no redundant work.

The wavefront expands from all sources simultaneously, like dropping three stones into a pond at once. Each cell is claimed by the nearest source, and every cell is visited exactly once. Total work: O(n), regardless of how many sources there are.

At each step, tap the fresh oranges you think rot next, then confirm. Notice how the wavefront feels like a single unified expansion, not three separate ones.

The key insight connects back to the distance invariant from the BFS shortest-path lesson: the BFS queue is always sorted by distance. When you place all sources in the queue at distance 0, BFS processes them all before touching any distance-1 node. Then all distance-1 nodes before any distance-2 node. The wavefront expansion is identical to single-source BFS -- the only difference is that the “source” is a set of nodes rather than a single node.

This is why no cell is ever visited twice. When a cell gets enqueued, it is marked visited immediately (mark-on-push, just like you learned in the visited-set lesson). If a second source's wavefront reaches the same cell later, it finds the cell already visited and skips it. The first source to reach a cell “wins,” and its distance is guaranteed to be the minimum because BFS processes distances in order.

The elegance is in what does not change. The BFS main loop -- dequeue, expand neighbors, enqueue unvisited ones -- is exactly the same as single-source BFS. The only modification is the initialization: instead of queue = [source], you write queue = [...allSources]. One line changes. The algorithm, the invariant, and the correctness proof are identical.

This pattern -- “change the init, keep the loop” -- is a recurring theme in BFS problems. Multi-source BFS, 0-1 BFS, bidirectional BFS: they all modify the starting conditions and leave the core algorithm untouched.

Here is the mental model that makes multi-source BFS click permanently -- and makes it trivial to prove correct.

Imagine adding a virtual node S* to the graph. S* has a 0-weight edge to every source node. Now run standard single-source BFS from S*. The first step dequeues S* and enqueues all sources at distance 0. From that point forward, the traversal is identical to what you just saw: all sources expand simultaneously, wavefronts merge, each cell is visited once.

Multi-source BFS is single-source BFS from a supernode. The supernode is an explanatory fiction -- you never create it in code. Instead, you enqueue all sources directly at distance 0, which is equivalent to starting from S* and taking one implicit step.

Why is this model useful? Because it lets you reuse everything you already know about BFS correctness. Single-source BFS finds shortest distances from one node? Then multi-source BFS finds shortest distances from the nearest source -- because that is exactly what BFS from S* computes. The distance from S* to any cell equals the minimum distance from any real source to that cell, since S* reaches every source in 0 steps.

Tap through the visualization below to see the supernode model in action. Notice how removing S* and starting with the sources directly produces the exact same BFS tree.

Now solve a trickier grid. This one has walls (empty cells that block the infection) and an edge case you need to watch for: what happens when a fresh orange is completely surrounded by walls? BFS cannot reach it. The answer to “how many minutes until all oranges are rotten?” becomes -1 -- impossible.

This edge case is the difference between a correct solution and a solution that passes most test cases. After BFS finishes, you must scan the grid for any remaining fresh oranges. If even one exists, the answer is -1. If all oranges are rotten, the answer is the maximum distance BFS assigned to any cell.

Step through the BFS minute by minute. Predict which oranges rot at each step and watch for the unreachable orange. The moment BFS terminates with fresh oranges still on the grid, that is your signal.

Same grid, same sources. Per-source BFS on the left, multi-source BFS on the right. Both produce the same answer -- the minimum time for every orange to rot. But the work required is dramatically different.

On the left, each source launches a full traversal. Cells get re-explored by each wavefront, and the operation counter climbs with every redundant visit. On the right, all sources share a single traversal. Each cell is visited exactly once, and the counter stays lean.

Watch the operation counters race. On this small grid, the per-source approach might do 2-3x the work. On a 200x200 grid with 50 sources, the ratio can exceed 50x. The asymptotic difference is O(k * n) versus O(n) -- the number of sources drops out entirely in the multi-source version.

This is the kind of optimization that separates an O(n) solution from a TLE (Time Limit Exceeded) on competitive programming judges. Same correctness, same idea, wildly different performance.

Multi-source BFS appears in a surprising number of problems once you know what to look for. The telltale sign: multiple starting points that all need to spread or measure distance simultaneously.

Classic examples: Rotting Oranges (LC 994) -- multiple rotten oranges spread infection simultaneously. Walls and Gates (LC 286) -- fill every empty room with the distance to the nearest gate, where gates are the sources. 01 Matrix (LC 542) -- find the distance from every cell to the nearest 0, where all 0-cells are sources. Shortest Bridge (LC 934) -- find the shortest distance between two islands, using all cells of one island as sources.

The pattern: whenever the problem asks “distance from the nearest X” for multiple X's, enqueue all X's at distance 0 and run a single BFS. If the problem asks “how long until everything is reached from multiple starting points,” same technique.

For each problem below, decide: multi-source BFS or not?

You have seen the waste of per-source BFS, felt the efficiency of the unified wavefront, and understood the supernode model. Now construct the code yourself.

Multi-source BFS is single-source BFS with exactly one structural change: the initialization. Instead of seeding the queue with one node, you seed it with all sources. Everything else -- the main loop, the neighbor expansion, the visited check -- is identical. This is what makes the pattern so powerful and so easy to get wrong: the temptation is to reach for a more complex approach (run BFS from each source, merge results) when the simple approach (change one loop) is both faster and correct.

The initialization is where the supernode insight becomes concrete code. You are essentially writing the edges from the virtual supernode S* to each real source -- except you skip S* entirely and just enqueue the sources directly at distance 0. That one loop replaces what would otherwise be k separate BFS calls. Once the sources are in the queue, BFS does not know or care that there were multiple starting points. It just processes them in FIFO order, exactly like it would process the neighbors of any single node.

Three blanks. Two are in the initialization: iterating over all sources and enqueuing each one at distance 0. The third is in the main loop, where the BFS expansion happens exactly as it would in single-source BFS. If you can fill all three, you can solve any multi-source problem by identifying the sources and writing one init loop.

Three questions to cement the multi-source pattern.

The pattern you just learned has an unusual property: it is simultaneously one of the simplest BFS modifications and one of the most frequently tested in interviews. Rotting Oranges (LC 994), Walls and Gates (LC 286), 01 Matrix (LC 542), Shortest Bridge (LC 934) -- these are all top-100 interview problems, and they all reduce to multi-source BFS. The students who struggle with them almost always make the same mistake: they try to run BFS from each source separately, then wonder why their solution times out on large inputs. The fix is not a clever optimization -- it is recognizing that the problem is multi-source BFS and that the initialization is the only thing that changes.

The first question tests whether you understand why all sources start at distance 0 (the supernode model). The second asks you to identify a multi-source BFS problem in the wild -- can you spot the telltale “distance from nearest X” phrasing? The third tests the edge case: what happens when multi-source BFS terminates but unreachable nodes remain? This last one is the detail that separates a solution that passes 95% of test cases from one that passes all of them.

The core insight fits in one sentence: same algorithm, different initialization. But knowing when to apply it and what can go wrong is what separates understanding from memorization.