Rotting Oranges
Spread rot from every source at once, one queue pass per minute, and decide with the fresh count.
Examples
The last orange to turn is (2, 2), at minute 4.
The orange at (2, 0) has only empty cells beside it, so it never rots.
Nothing is fresh, so no minutes pass.
Problem Understanding
A grid holds three kinds of cell: 0 is empty, 1 is a fresh orange and 2 is a rotten one. Every minute, each rotten orange rots the fresh oranges directly above, below, left and right of it — diagonals do not count.
- Goal: the minutes until nothing fresh is left, or
-1if that never happens (LeetCode 994). - Input:
[[2,1,1],[1,1,0],[0,1,1]]. Output:4. - Input:
[[2,1,1],[0,1,1],[1,0,1]]. Output:-1— the orange at(2, 0)has only empty cells beside it. - Input:
[[0,2]]. Output:0— nothing is fresh, so no time has to pass.
Every rotten orange spreads during the same minute, which is what makes this a multi-source BFS rather than a search from one starting point.
Algorithm Strategy
One scan to set up, then one pass of the queue per minute.
- Scan once. Put every rotten orange in the queue and count the fresh ones. Both facts come out of the same pass.
- Answer the easy case. No fresh oranges means no time has to pass: return 0 before the loop.
- One minute per pass. Read the queue's size, then dequeue exactly that many oranges. Those are the ones that were rotten when the minute began, so everything they rot turns at the same time.
- Rot the neighbours. For each of the four directions, a cell that is on the grid and still
1becomes2, decreases the fresh count, and joins the queue for the next minute. - Decide. When the queue drains,
fresh == 0means the answer is the minute count; anything left fresh could never be reached, so the answer is-1.
Why the fresh count and not the grid. Checking "is anything still fresh" by rescanning the grid each minute would make the method quadratic in the cell count. One integer, decremented as each orange turns, answers the same question in O(1).
Interactive Visualization
The opening scan is stepped through cell by cell, because that is where both the queue and the fresh count come from. Then each minute is one pass: every orange that was rotten when the minute began is dequeued, and the ones it rots are stamped with the minute they turned. Try Two sources, where rot spreads from both corners at once and the middle turns sooner than either could manage alone.
Dry Run
Input: [[2,1,1],[1,1,0],[0,1,1]]
The scan finds one rotten orange, at (0, 0), and counts 6 fresh.
| Minute | Dequeued | What rots | fresh after |
|---|---|---|---|
| 1 | (0, 0) | (0, 1) and (1, 0) | 4 |
| 2 | (0, 1), (1, 0) | (0, 2) and (1, 1), both from (0, 1) — (1, 0) has nothing fresh beside it | 2 |
| 3 | (0, 2), (1, 1) | (2, 1), from (1, 1) — (0, 2) is walled in by the empty cell at (1, 2) | 1 |
| 4 | (2, 1) | (2, 2) | 0 |
The queue empties with fresh == 0, so the answer is 4.
Note minute 3: (1, 2) is an empty cell, so nothing rots through it. The only cell to turn that minute is (2, 1), reached downwards from (1, 1).
Edge Cases & Common Mistakes
Edge Cases:
- Nothing fresh: return 0 without entering the loop, even when the grid is all rotten or all empty.
- A fresh orange nothing can reach: the queue drains with
fresh > 0, which is the-1case. - No rotten orange at all: the queue starts empty, so the first
whilecheck fails immediately —-1, unless there was nothing fresh either. - A single cell:
[[1]]is -1 and[[2]]is 0.
Common Mistakes:
- Starting the queue with one rotten orange. Every source spreads during the same minute; queueing only the first makes the rot travel through the others rather than from them.
- Counting a minute for the last layer. Stopping the loop on
fresh > 0is what keeps the answer from being one too many — the layer that rots nothing must not add a minute. - Forgetting
-1altogether, which passes every connected example and fails the moment a fresh orange is walled off.
Solution Code
One scan to count the fresh and queue every rotten orange, then one pass per minute (LeetCode 994).
Rotting Oranges Code
1var orangesRotting = function(grid) {2 const rows = grid.length, cols = grid[0].length;3 const queue = [];4 let fresh = 0;5 for (let r = 0; r < rows; r++) {6 for (let c = 0; c < cols; c++) {7 if (grid[r][c] === 2) {8 queue.push([r, c]);9 } else if (grid[r][c] === 1) {10 fresh++;11 }12 }13 }14 if (fresh === 0) {15 return 0;16 }17 const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];18 let minutes = 0;19 let head = 0;20 while (head < queue.length && fresh > 0) {21 minutes++;22 const size = queue.length - head;23 for (let i = 0; i < size; i++) {24 const [r, c] = queue[head++];25 for (const [dr, dc] of directions) {26 const nr = r + dr, nc = c + dc;27 if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || grid[nr][nc] !== 1) {28 continue;29 }30 grid[nr][nc] = 2;31 fresh--;32 queue.push([nr, nc]);33 }34 }35 }36 return fresh === 0 ? minutes : -1;37};