Rotten Oranges
Rotten oranges rot their 4-neighbours each minute. Return minutes until all rot, or −1 if some never do.
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 10
- grid[i][j] is 0, 1, or 2.
Intuition
In rotten oranges, every rotten orange rots its four neighbours each minute, and you must report the minute everything has rotted — or −1 if some fresh orange is unreachable. The wrong instinct is to process the rotten oranges one at a time, spreading each fully before moving to the next. That gives the wrong answer, because rot spreads from all rotten oranges simultaneously. An orange between two sources rots from whichever reaches it first. The right model is a multi-source BFS: seed the queue with every initially rotten cell before starting, rather than with a single origin. Then each BFS layer corresponds to one minute of elapsed time, and because BFS explores in layers, every orange is reached at the earliest minute any source could reach it — automatically, with no comparison between sources. Two details determine correctness: - Count the fresh oranges up front, and decrement as each rots. If the count is not zero when the queue empties, some orange was unreachable and the answer is −1. - A grid with no fresh oranges at all returns 0, not the number of minutes — there is nothing to wait for, even if the grid is full of rotten ones. That second case is easy to miss and is usually the failing test.
Multi-source BFS. Every rotten orange starts in the queue at time 0, so the wave spreads from all of them simultaneously and the last node dequeued carries the answer. Whenever a spread happens from several starting points at once, seed them all rather than running BFS once per source.
Approach
Before reading on: price up what the direct approach costs here, then ask what one visit per cell or vertex would have to mark so nothing is counted twice. Aim for O(R·C) time and O(R·C) space.
Seed every rotten cell before starting
Scan the grid once, pushing all rotten cells into the queue at time 0 and counting the fresh ones. Seeding all sources together is what makes the timing correct — spreading from one source at a time would overcount the minutes.
Understand a BFS layer as a minute
Each layer of the BFS is one minute of spreading. A cell reached in layer t rots at minute t, and BFS guarantees that is the earliest any source could reach it, so no comparison between competing sources is ever needed.
Rot fresh neighbours and decrement
When processing a cell, check its four neighbours; any fresh one becomes rotten at the current time plus one, is pushed onto the queue, and the fresh counter drops by one. Mark it rotten immediately in the grid so it is not enqueued twice from another direction.
Track the maximum time reached
Keep the largest time assigned to any cell. When the queue empties, that value is the minute the last orange rotted, which is the answer when everything did rot.
Check the fresh count at the end
If the counter is still above zero, some fresh orange was walled off from every source — return −1. This test is the only thing distinguishing a solvable grid from an unsolvable one.
Handle the no-fresh-oranges case
If the initial fresh count is zero, return 0 immediately. Nothing needs to rot, so no time passes — this edge case is the usual cause of a wrong answer when the rest of the logic is right.
Cost of the sweep
Every cell is enqueued and dequeued at most once, giving O(rows × cols) time and the same bound on space for the queue in the worst case, when the whole grid starts rotten.
Solution & live demo
Common pitfalls
Running BFS from each rotten orange separately
for each rotten: bfs(...) return max(times)
for r, c in all rotten: q.append((r, c, 0))
Separate runs cost O(sources × cells) and need a per-cell minimum across runs to be correct. Seeding every source at time 0 makes one pass compute the true simultaneous spread.
Not checking for unreachable fresh oranges
return t
return t if fresh == 0 else -1
Fresh oranges walled off from any rotten one never rot, and the answer must be −1. Tracking the fresh count and verifying it hits zero is what distinguishes "finished" from "stalled".
Marking cells rotten only when dequeued
r, c, t = q.popleft() grid[r][c] = 2
grid[nr][nc] = 2 q.append((nr, nc, t + 1))
A cell reachable from two rotten neighbours gets enqueued twice before either is processed, so it's counted twice and can be assigned a later time. Marking at enqueue time makes each cell enter the queue exactly once.
Edge cases
Answer 0 — nothing to wait for.
Never enqueued; fresh count stays positive → −1.