Appearance
4.20.6 — Rotting Oranges
LeetCode 994 · Medium
The problem
A grid holds 0 (empty), 1 (fresh orange) and 2 (rotten orange). Every minute, a rotten orange rots each fresh orange directly adjacent to it. Return the number of minutes until no fresh orange remains, or -1 if that never happens.
2 1 1 2 2 1 2 2 2 2 2 2
1 1 0 → 2 1 0 → 2 2 0 → 2 2 0 → 4 minutes
0 1 1 0 1 1 0 2 1 0 2 2The pattern
Three signals point at BFS, and all three are worth recognising:
- "Every minute" — the process happens in discrete rounds.
- "Adjacent" — each round spreads by exactly one step.
- The answer is a number of steps, not a set of cells.
BFS explores in rings — everything one step away, then everything two steps away — so the ring number is the minute number.
And there are many starting points, since every rotten orange spreads at once. That is multi-source BFS: put every source in the queue before the loop begins, all at distance zero. They then expand together, and each fresh orange is reached by whichever rotten orange is nearest.
No extra machinery. Multi-source BFS is single-source BFS with a fuller initial queue.
The ELI5 Analogy
Imagine a classroom full of students. A few students come to school with a highly contagious cold (the rotten oranges). Every hour (minute), any sick student coughs on the healthy students sitting directly next to them (up, down, left, right), making them sick too. To figure out how long it takes for the whole class to get sick, you don't trace one sick student's path completely and then start over with another. Instead, you say: "Hour 1: all originally sick students cough. Hour 2: the newly sick students cough." You process it in waves, all at the same time.
What about a Brute Force Approach?
A brute-force simulation without a queue would look like: while fresh_oranges > 0: 1. Scan the ENTIRE grid to find rotten oranges. 2. Check their neighbors. 3. If a neighbor is fresh, mark it as 'about to rot'. 4. Scan the grid AGAIN to change 'about to rot' to 'rotten'. If you have a 100x100 grid, and it takes 50 minutes to rot, you are rescanning 10,000 cells 50 times (500,000 operations) when you only needed to touch each cell once or twice. BFS completely skips the dead space and empty cells.
The solution
python
from collections import deque
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
rows, cols = len(grid), len(grid[0])
queue = deque()
fresh = 0
for r in range(rows): # seed ALL sources first
for c in range(cols):
if grid[r][c] == 2:
queue.append((r, c))
elif grid[r][c] == 1:
fresh += 1
if fresh == 0:
return 0 # nothing to rot
minutes = 0
while queue and fresh > 0:
minutes += 1
for _ in range(len(queue)): # exactly one minute
r, c = queue.popleft()
for nr, nc in ((r+1,c), (r-1,c), (r,c+1), (r,c-1)):
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
grid[nr][nc] = 2 # mark on ENQUEUE
fresh -= 1
queue.append((nr, nc))
return minutes if fresh == 0 else -1ts
function orangesRotting(grid: number[][]): number {
const rows = grid.length, cols = grid[0].length;
let queue: Array<[number, number]> = [];
let fresh = 0;
for (let r = 0; r < rows; r++)
for (let c = 0; c < cols; c++) {
if (grid[r][c] === 2) queue.push([r, c]);
else if (grid[r][c] === 1) fresh++;
}
if (fresh === 0) return 0;
let minutes = 0;
while (queue.length && fresh > 0) {
minutes++;
const next: Array<[number, number]> = [];
for (const [r, c] of queue) {
for (const [nr, nc] of [[r+1,c],[r-1,c],[r,c+1],[r,c-1]] as [number,number][]) {
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === 1) {
grid[nr][nc] = 2;
fresh--;
next.push([nr, nc]);
}
}
}
queue = next;
}
return fresh === 0 ? minutes : -1;
}Five details, and each is a place people lose marks.
Seed every rotten orange before the loop. Running BFS once per source would be far slower and would need the minimum taken afterwards.
for _ in range(len(queue)) freezes the level, so one iteration of the outer loop is exactly one minute. This is the same line as 4.14.8 Level Order Traversal.
Count the fresh oranges up front, and decrement as they rot. At the end, any left means some were unreachable → -1. Counting them again at the end would also work and costs another pass.
if fresh == 0: return 0 before the loop. A grid with no fresh oranges takes zero minutes, including a completely empty grid. Without this, a grid of only rotten oranges would still run one round and return 1.
while queue and fresh > 0. Stopping as soon as the last orange rots avoids counting one extra minute for the final round that changes nothing. Alternatively, run the loop to exhaustion and return minutes - 1 — but that needs its own guard for the zero case, which is uglier.
Mark on enqueue, not on dequeue. A cell reached by two rotten neighbours in the same minute would otherwise be queued twice.
Code Walkthrough & Trace
Consider a 1D grid [2, 1, 1]
| Step | Action | Queue | fresh | minutes |
|---|---|---|---|---|
| 1 | Initial scan. Seed rotten at (0,0). | [(0,0)] | 2 | 0 |
| 2 | while loop starts. minutes++. | [(0,0)] | 2 | 1 |
| 3 | Outer for processes 1 element (the size of queue). Pop (0,0). | [] | 2 | 1 |
| 4 | Check neighbors. (0,1) is 1. Rot it (grid[0][1] = 2). | [(0,1)] | 1 | 1 |
| 5 | while loop continues. minutes++. | [(0,1)] | 1 | 2 |
| 6 | Pop (0,1). Check neighbors. (0,2) is 1. Rot it. | [(0,2)] | 0 | 2 |
| 7 | while loop continues? No, fresh is now 0. | [(0,2)] | 0 | 2 |
| 8 | Return minutes | 2 |
Key lines explained:
for _ in range(len(queue)):- This freezes the current size of the queue. If there are 3 rotten oranges, it pops exactly 3 times. Any newly rotten oranges appended to the queue won't be processed until the next iteration of thewhileloop.
Complexity
O(rows \times cols) time — every cell enters the queue at most once. To derive this: the initial double loop to seed the queue takes O(rows \times cols). During the BFS, each cell is enqueued at most once (because we mark it as rotten 2 immediately upon discovering it, and only fresh oranges 1 are enqueued). Therefore, the while loop processes at most rows \times cols elements, doing O(1) work for each. Total time is linear with respect to the grid size.
O(rows \times cols) space for the queue. In the worst case, the queue might hold all cells in the grid at the same time (e.g., if every single cell was a rotten orange initially). Even in a typical BFS expansion, the maximum perimeter (number of elements in the queue) is bounded by O(rows \times cols).
Where this goes next
Multi-source BFS is a small idea that solves a lot:
- Walls and Gates — distance from every cell to its nearest gate. Identical code with different labels. 4.20.7.
- 01 Matrix — distance from each cell to the nearest zero. Seed every zero.
- As Far from Land as Possible — seed every land cell and take the last ring reached.
- Shortest Bridge — flood one island to find it, then BFS outward from all of it at once until you hit the other.
The tell is always the same: the question is "distance to the nearest X" for many X at once. Seed them all and run BFS once.
What the interviewer will push on
"Why BFS and not DFS?" The answer is a number of steps, and BFS explores by distance so the ring number is the answer. DFS would find a route, not the shortest.
"How do you handle many starting points?" All of them in the queue before the loop.
"How do you know when a minute has passed?" The frozen level size.
"How do you detect the impossible case?" Fresh oranges remaining after the queue drains — they were unreachable.
"What if the grid has no fresh oranges at all?" Zero minutes, and it needs the explicit guard.
"What if rotting spread diagonally too?" Eight neighbours instead of four. Nothing else changes, which is a good demonstration that the algorithm does not care about the geometry.
One thing to volunteer: name the technique — "this is multi-source BFS, so every rotten orange goes into the queue before the first round" — and say that the ring number is the minute. Those two sentences are the whole solution.
Next: 4.20.7 Walls and Gates — the same algorithm, filling in distances instead of counting rounds.