Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Rot spreads simultaneously from every rotten orange, so this is multi-source BFS. Seed the queue with all initially rotten oranges, then process the grid level by level — each level is one minute. Count fresh oranges; if any remain after BFS, return -1. The answer is the number of BFS levels minus one. O(rows × cols).
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you recognise simultaneous spread as multi-source BFS (seed all sources together) and correctly map BFS levels to elapsed minutes, plus the unreachable (-1) and zero-fresh (0) cases.
Where candidates slip
Running BFS from one rotten orange at a time (wrong timing), forgetting to return -1 when fresh oranges are stranded, or off-by-one on the minute count.
How to stand out
State 'multi-source BFS, levels = minutes', seed all rotten cells, count fresh, handle the zero-fresh and unreachable cases explicitly, and note the level-size snapshot is what separates minutes cleanly.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewMin minutes for all oranges to rotAny fresh to rot?NoYesExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 1 · Optimal
Multi-Source BFS (Optimal)
1Hint 1Explore hintHide hint
The rot spreads from every rotten orange at the same time. If you started BFS from just one, your timing would be wrong — how do you start from all of them at once?
2Hint 2Explore hintHide hint
Put every initially rotten orange in the queue first, and count the fresh oranges. Then BFS one level at a time; each level is a minute.
3Hint 3Explore hintHide hint
After each level, the newly rotted oranges form the next level's sources. When BFS stops, if any fresh remain they were unreachable → return -1; otherwise return the number of levels processed.
A · Core idea
Model the minute-by-minute spread as breadth-first layers radiating from all rot at once.
Seed every source, count the targets. Scan the grid once: enqueue every rotten orange (value 2) and tally the fresh ones (value 1). Seeding all rotten oranges simultaneously is the crux — rot doesn't take turns, so a single-source BFS would over-count the time. This is precisely what 'multi-source BFS' means.
Process level by level; each level is a minute. The standard BFS-by-levels trick: before draining the queue, snapshot its current size k. Those k cells are everything rotten at this minute. Process exactly them, rotting any fresh neighbour (set it to 2, decrement the fresh count, enqueue it). After finishing the snapshot, increment the minute counter. The newly enqueued oranges are next minute's sources.
Stop conditions and the answer. Continue while the queue is nonempty and fresh oranges remain. When BFS ends: if fresh > 0, some orange was never reached (blocked by empties) → return -1. Otherwise the minute counter is the time the last orange rotted.
The two boundary cases. If there are zero fresh oranges at the start, return 0 — nothing needs to rot, no matter how many rotten oranges exist. And rot a neighbour at enqueue so it isn't counted or processed twice.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
grid = [[2,1,1],[1,1,0],[0,1,1]]Live grid state
Cells change as the traversal moves
min 1rot (0,1),(1,0)
4C · Code with teaching comments
D · Why it works and complexityO(m × n) timeO(m × n) spaceOpen the invariant and proofExplore the proofHide the proof
Multi-source BFS computes, for every cell, the shortest distance to the nearest source — all in one sweep. The deepest level reached is the time the farthest reachable orange rots. Counting levels (not individual cells) is what converts a flood into a clock.
ComplexityO(m × n) time, O(m × n) space — Every cell is enqueued at most once and processed once → O(m·n). The initial scan to seed and count is also O(m·n). The queue holds at most all cells → O(m·n) space.
E · Edge cases and pitfalls7no fresh oranges [[0,2]] — fresh == 0 at start → return 0 before any BFS.Explore edge casesHide edge cases
Edge cases handled
no fresh oranges [[0,2]]fresh == 0 at start → return 0 before any BFS.no rotten oranges, some freshQueue empty; BFS never runs; fresh > 0 → return -1.isolated fresh orangeBFS exhausts queue with fresh > 0 → -1.
Pitfalls
- Running BFS from one rotten orange at a time — produces wrong minute counts.
- Forgetting the fresh == 0 early return — can return a spurious nonzero minute.
- Not snapshotting the level size — mixes minutes together and over-counts time.
- Forgetting to return -1 when fresh oranges remain unreachable.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int orangesRotting(int[][] grid) { int m = grid.length, n = grid[0].length, fresh = 0; Queue<int[]> q = new LinkedList<>(); for (int r = 0; r < m; r++) { for (int c = 0; c < n; c++) {Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Single-source instead of multi-source
Rot spreads from every rotten orange at once. BFS from one source at a time serialises the spread and reports too many minutes.
Explore the code comparisonHide the code comparison
Single-source instead of multi-source
Rot spreads from every rotten orange at once. BFS from one source at a time serialises the spread and reports too many minutes.
Don't write this
for (r, c) in rotten_cells:
bfs_from(r, c) # serial — wrong timing
# minutes accumulated separately per sourceWrite this instead
q = deque(rotten_cells) # ALL sources seeded together
while q and fresh:
minutes += 1
for _ in range(len(q)):
... # spread one minute from every current source2Forgetting the unreachable (-1) check
If a fresh orange is walled off by empty cells, BFS can't reach it. Returning the minute count instead of -1 is wrong.
Explore the code comparisonHide the code comparison
Forgetting the unreachable (-1) check
If a fresh orange is walled off by empty cells, BFS can't reach it. Returning the minute count instead of -1 is wrong.
Don't write this
// BFS ends
return minutes; // ignores stranded fresh orangesWrite this instead
// BFS ends
return fresh == 0 ? minutes : -1;Revise
Carry the pattern into the interview
Pattern to remember
Multi-source BFS, levels = elapsed minutes
Code pattern to memorize
queue = all rotten cells; fresh = count of fresh
minutes = 0
while queue and fresh:
minutes += 1
for each cell in current level:
for fresh neighbour: rot it, fresh--, enqueue
return -1 if fresh else minutesRules to remember
- 1Seed ALL rotten oranges before starting — rot spreads from every source at the same time.
- 2Process the queue level by level (snapshot the level size); each completed level = one minute elapsed.
- 3Track the fresh count; if it's nonzero when BFS ends, some orange is unreachable → return -1.
- 4Rot a neighbour (set to 2) AT ENQUEUE so it isn't processed twice.
- 5Edge case: 0 fresh at the start → answer is 0 minutes, regardless of rotten oranges.
Use this pattern when
- Simultaneous spread / infection / fire from multiple sources on a grid
- 'Minimum time for all cells to be affected' problems
- Shortest distance from the nearest of many sources (multi-source BFS)
- Level-order grid traversal where each level is a time step
Choose another pattern when
- Single source shortest path → ordinary BFS
- Weighted spread times → Dijkstra, not unit-step BFS
- You need the actual path, not just time → track predecessors
Interview takeaway
Rotting Oranges is the textbook multi-source BFS: load every source into the queue at once and let levels count time. The same 'seed all sources, count levels' template solves Walls and Gates, 01 Matrix, and any shortest-time-to-fill-the-grid question.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternMulti-source BFS where levels count time. Seed every source at once and process the grid level by level. Same family as Walls and Gates, 01 Matrix, and As Far from Land as Possible.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Walls and GatesComing soonMulti-source BFS from all gates filling each empty room with its distance to the nearest gate.
- 01 MatrixComing soonMulti-source BFS seeded from all 0s to compute each 1's distance to the nearest 0.
- As Far from Land as PossibleComing soonMulti-source BFS from all land cells; the deepest water cell is the answer.
- Number of IslandsSame grid-BFS skeleton; count components instead of timing a spread.