← Visualizers
Graphs · Multi-source BFS LeetCode 994

Rotting Oranges / visualized

Multi-source BFS: every source is seeded before the first pop, so one sweep gives every cell its distance to the nearest source. The fresh counter is what separates finished from unreachable.

Execution

idle
INVARIANT Seed ALL sources at t=0 before first pop. Concentric waves expand simultaneously; remaining fresh count separates unreachable (-1) from complete.
Spreading Wave (Minute t)
Next Wave (Minute t+1)
Press Run to begin.
0 / 0
Speed

Java · running line

spreading now in wave queue already rotten empty cell
INTERVIEW SCRIPT

How to Explain Rotting Oranges to an Interviewer

1. Multi-Source BFS Seeding

"All rotten oranges must be enqueued at time $t=0$ before processing begins. They radiate outwards in lockstep concentric waves."

2. The Fresh Orange Counter

"We maintain a fresh count. When a fresh orange rots, we decrement fresh--. At the end, if fresh > 0, isolated oranges exist and we return -1."

3. Why minutes - 1?

"The final wave rots the last orange, but its subsequent empty loop increments minutes one extra time before discovering the queue is empty. Hence, minutes - 1."

4. Complexity Mastery

"Every cell is visited and rotted at most once. Time is strictly $O(m \cdot n)$ and auxiliary queue space is $O(m \cdot n)$."

O(m·n) time and space  ·  the answer is minutes - 1 because the sources themselves occupy level 1 and rot nothing; a fresh orange left at the end means it was never reachable, which is -1, not a larger number.