Multi-source BFS

41 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

A grid of oranges: 2 means rotten, 1 fresh, 0 empty. Each minute every rotten orange rots its fresh neighbours (up, down, left, right). How many minutes until no fresh orange remains? Grid: row 0 is 2 1 1, row 1 is 1 1 0, row 2 is 0 1 1. By hand you redraw the grid minute by minute: after minute 1 the two neighbours of the rotten one are rotten, after minute 2 two more, and so on until minute 4 when the last one in the bottom right goes.

Redrawing the whole grid each minute costs the grid size per minute, and the number of minutes can be as large as the grid, so about (m × n)² steps in the worst case. Also, if several oranges start rotten, you must spread from all of them at the same time; handling one source at a time and taking the minimum per cell works but repeats the whole spread once per source.

Build the structure, one piece at a time

Piece one: a queue of (cell, minute) pairs, and a way to mark a cell as rotten so that it is never processed twice. Writing 2 into the grid is the mark.

Piece two: seed the queue with every rotten orange at minute 0, all at once. This is the whole trick. A queue served from the front processes all minute-0 cells, then all minute-1 cells, and so on, so the spread from all sources advances in lockstep, exactly like the redrawing.

Piece three: pop a cell; for each fresh neighbour, mark it rotten and push it with minute + 1. Remember the largest minute pushed. At the end, if any fresh orange is still fresh, the answer is −1; otherwise it is the largest minute.

Queue empty, largest minute 4, no fresh orange left: answer 4.

Why it is correct

Think of all the sources as connected to one imaginary super-source by zero-length edges. Breadth-first search from the super-source then gives every cell its distance to the nearest source, because BFS on an unweighted graph finds shortest distances. Seeding the queue with all sources at minute 0 is exactly BFS from the super-source with the first step already taken.

minute(cell) = min over sources s of distance(s, cell), and the answer = max over cells of minute(cell)

The invariant that makes the queue work: cells are popped in non-decreasing minute order, and all cells of minute d are popped before any of minute d + 1, because pushes always go to the back with a minute one larger than the front. So the first time a cell is marked, it is from a cell at the smallest possible minute, and the recorded minute is the true one.

Why it is fast

Each cell is pushed and popped at most once, with four neighbour checks: O(m × n). Redrawing per minute was up to quadratic in the grid size, and running one BFS per source would multiply by the number of sources. Memory is the queue, at most the grid size.

How to recognise it in an interview

"Spreads each minute from several starting points", "distance to the nearest 0 for every cell", "fill each empty room with the distance to its nearest gate", "how far from land is the farthest water". Say: "I will seed a BFS queue with all sources at distance 0; the first visit of each cell is its distance to the nearest source." Rotting Oranges is this exactly. 01 Matrix seeds with every 0 and writes the distance into each 1. Walls and Gates seeds with every gate. Shortest Distance from All Buildings is the exception that needs one BFS per building, because it wants the sum of distances, not the minimum.

02The idea in one line

Seed the queue with every source; the first visit is the nearest source.

Reach for it when: Rotting oranges, 01 matrix, walls and gates, shortest distance from buildings.

Cost: O(mn) time.

03The walk-through, step by step

The video works one example: Rotting Oranges on [[2,1,1],[1,1,0],[0,1,1]]. These are its captions in order, so you can follow without the video or check a step you missed.

1. Seed the queue with every rotten orange at minute 0
2. Pop (0,0) at minute 0: it rots 2 neighbours at minute 1
3. Pop (1,0) at minute 1: it rots 1 neighbour at minute 2
4. Pop (0,1) at minute 1: it rots 1 neighbour at minute 2
5. Pop (1,1) at minute 2: it rots 1 neighbour at minute 3
6. Pop (0,2) at minute 2: no fresh neighbour left
7. Pop (2,1) at minute 3: it rots 1 neighbour at minute 4
8. Pop (2,2) at minute 4: no fresh neighbour left
9. Queue empty, no fresh orange remains: answer 4 minutes
10. Each cell enters the queue once: O(m·n)

04Asked at Google

6 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Graphs: Grid flood fill (components), BFS shortest path (unweighted), BFS over an augmented state, 0-1 BFS (deque), DFS three-colour cycle detection, Topological sort (Kahn's), Union–Find (disjoint sets), Dijkstra (weighted shortest path), Bellman–Ford with k rounds, Minimum spanning tree, Bipartite colouring, Eulerian path (Hierholzer), Bridges / articulation (low-link), Clone / traverse with a visited map, Implicit graph (states as nodes).