STEP 15 · GRAPHS · MULTI-SOURCE BFS · MEDIUM

Rotting Oranges

WHAT IT SAYS

Rot spreads from rotten oranges to adjacent fresh ones every minute; find how many minutes until no fresh orange remains, or -1 if some never rot.

WHAT IT'S REALLY ASKING

"When does a given orange rot? At a time equal to its distance from the NEAREST rotten one — the closest source wins the race. 'Distance to the nearest of many sources' is exactly what BFS computes if you start it from ALL sources at once: seed every rotten orange into the queue at minute zero, and the level-by-level expansion IS the simulation."

THE INSIGHT LADDER — FROM BRUTE FORCE TO OPTIMAL

Simulate minute by minute with full scans

O(minutes × m·n) — up to O((mn)^2) on a long snaking corridor

Repeat until stable: scan the entire grid, find every fresh orange adjacent to a currently-rotten one, mark them all to rot (in a separate pass or buffer, to avoid same-minute chaining), increment the clock.

WHERE THE WORK IS WASTED — Each minute's scan re-examines the whole grid, but almost all of it is dead territory: cells rotten for ages (their neighbours long since infected) and cells nowhere near the front. The only cells that can CHANGE this minute sit on the frontier — the boundary between rotten and fresh — and the scan's price is paid for rediscovering that frontier from scratch every minute, when last minute's newly-rotted cells ARE this minute's frontier, already known the moment they rotted. The simulation forgets its own most recent output and buys it back with a full scan.

KEY OBSERVATION — THE UNLOCKlink

Seed all sources at once; BFS levels are the minutes.

Two facts fuse into the algorithm. First: the rot time of a fresh orange equals its grid distance to the nearest initially-rotten orange. Induction on minutes — an orange rots at minute t exactly when some neighbour rotted at t-1, so rot time is 1 + the minimum neighbour rot time, which is the textbook recurrence for shortest distance in an unweighted graph, with the twist that there are MANY sources and the minimum ranges over all of them. Second: BFS computes single-source shortest distances because its queue processes cells in non-decreasing distance order — every cell is first reached via a shortest path. Now the trick that makes it multi-source, and understanding WHY it works matters more than the trick: seed the queue with ALL rotten oranges at distance 0. This is exactly equivalent to imagining one virtual super-source connected to every rotten orange by a zero-length edge and running ordinary single-source BFS from it — distances from the super-source ARE distances to the nearest real source. Nothing about BFS's correctness argument changes; the initial frontier just has many cells instead of one. The frontier bookkeeping the naive simulation kept losing is now the queue itself: each BFS level is exactly one minute's frontier, delivered for free by the previous level's expansion. Track levels either by stamping each cell with its rot minute as it's enqueued, or by processing the queue in level-sized batches (snapshot the size, pop that many). Every cell enters the queue at most once — mark-as-rotten on ENQUEUE, not on dequeue, or a cell gets queued by two racing neighbours. The -1 case needs no extra machinery: count fresh oranges up front, decrement on each infection; leftovers at the end were unreachable — a fresh orange sealed off by walls, which no amount of simulation would ever touch (and which the naive version discovers only by scanning until nothing changes).

Queue seeded with every rotten cell, level-batched expansion

O(m·n) time — each cell enqueued and dequeued once — O(m·n) queue space worst case

Scan once: enqueue all rotten cells, count fresh ones. BFS in level batches: pop a level, infect fresh 4-neighbours (mark rotten immediately, enqueue, decrement fresh count), minute++ after any level that infected someone. Answer: minutes elapsed if fresh count hit zero, else -1.

WHAT YOU TRADED — Multi-source BFS is strictly better than simulation here — same answers, one grid-read of cost — so the real trade is conceptual: you must see through the story (rot, fire, water) to the shortest-distance question underneath, because the moment spread rates DIFFER per cell (weighted edges) BFS breaks and Dijkstra takes over. The transferable lesson: 'simultaneous spread from many points' is always single-source BFS from a virtual super-source, and the simulation's minutes are just BFS levels wearing a costume.

WATCH THE IDEA RUN

2t0

minute (= BFS layer) 0

sources seeded together 2, at t=0

still fresh 9

Two oranges are already rotten. The instinct is to spread from one, then the other, and combine — but that is wrong AND unnecessary. Rot does not take turns. Every rotten orange spreads simultaneously, so a fresh orange rots at the time of the NEAREST source, not the first one you happened to process. So push ALL sources into the queue before starting, at distance 0. A BFS seeded with many sources computes, for every cell at once, the distance to its closest source — the sources race, and the queue arbitrates. One pass, not one per source.

step 1 / 5

THE PATTERN — SO YOU RECOGNIZE IT NEXT TIME

Super-Source BFS

YOU'LL SEE IT AGAIN WHEN

Something spreads uniformly per tick from MULTIPLE starting points, and the question is total time or per-cell arrival time.
Per-cell answer = distance to the NEAREST source — a minimum over sources, which one BFS from all seeds computes simultaneously.
A minute-by-minute simulation keeps rediscovering its frontier by scanning; the queue IS the frontier, carried forward for free.

SAME BLUEPRINT, DIFFERENT PROBLEM

01 Matrix / Distance of Nearest Cell Having 1Walls and GatesAs Far from Land as PossibleShortest Path in Binary Matrix (single-source contrast)

The bar isn't "solved it once." It's "could rebuild it from the observation."