LeetCode · #994
Rotting Oranges Solution
Given a grid of empty cells, fresh oranges, and rotten oranges, return the minimum minutes needed until no fresh orange remains — or -1 if some fresh orange can never rot.
01
Section One · Problem
Problem Statement
Each minute, every rotten orange infects its four direct neighbors. You must compute the first minute when the infection has spread to every reachable fresh orange. If any fresh orange is isolated from all rotten sources, the answer is -1.
Example
Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4 // Minute 0: one rotten source // Minute 4: every reachable fresh orange has rotted
Constraints
• 1 ≤ grid.length, grid[i].length ≤ 10 • grid[i][j] is 0, 1, or 2 • We need the minimum time across all simultaneous infection sources
02
Section Two · Brute Force
Minute-by-Minute Grid Rescan — O((m·n)²)
Simulate time directly. For each minute, scan the whole grid, collect every fresh orange that touches a rotten one, then rot all of them together. Repeat until no new orange changes state.
Why it works
The problem statement itself defines a round-based process. If we apply exactly one wave of infections per pass, the number of passes equals the number of minutes. Rotting all pending cells together preserves the simultaneous spread rule.
Why we can do better
Problem: We rescan the entire grid every minute, even though only the current infection frontier matters. BFS stores exactly that frontier in a queue, so each orange is processed once instead of being reconsidered every minute.
Java — full-grid simulation
import java.util.ArrayList;
import java.util.List;
class Solution {
public int orangesRotting(int[][] grid) {
int rows = grid.length, cols = grid[0].length;
int minutes = 0;
while (true) {
List<int[]> next = new ArrayList<>();
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] != 1) continue;
if ((r > 0 && grid[r - 1][c] == 2) ||
(r + 1 < rows && grid[r + 1][c] == 2) ||
(c > 0 && grid[r][c - 1] == 2) ||
(c + 1 < cols && grid[r][c + 1] == 2)) {
next.add(new int[] { r, c });
}
}
}
if (next.isEmpty()) break;
for (int[] cell : next)
grid[cell[0]][cell[1]] = 2;
minutes++;
}
for (int[] row : grid)
for (int cell : row)
if (cell == 1) return -1;
return minutes;
}
}
Python — full-grid simulation
class Solution:
def orangesRotting(self, grid: list[list[int]]) -> int:
rows, cols = len(grid), len(grid[0])
minutes = 0 while True:
nxt = []
for r in range(rows):
for c in range(cols):
if grid[r][c] != 1:
continue if ((r > 0 and grid[r - 1][c] == 2) or
(r + 1 < rows and grid[r + 1][c] == 2) or
(c > 0 and grid[r][c - 1] == 2) or
(c + 1 < cols and grid[r][c + 1] == 2)):
nxt.append((r, c))
if not nxt:
break for r, c in nxt:
grid[r][c] = 2
minutes += 1 for row in grid:
for cell in row:
if cell == 1:
return -1 return minutes
| Metric | Value |
|---|---|
| Time | O((m · n)²) — a full scan for every minute of spread |
| Space | O(m · n) worst case for cells collected in one minute |
03
Section Three · Optimal
Multi-Source BFS — O(m·n)
All rotten oranges start spreading at the same time, so treat every initial rotten cell as a BFS source. Put all of them in the queue at minute 0, count the fresh oranges, then expand level by level. One BFS layer equals one minute of rot.
💡 Mental model: Imagine several fires already burning in a field. You do not simulate one fire to completion and then the next. All flames expand outward together, one ring per minute. The queue holds the current fire boundary, and the next BFS layer is the next ring of burned cells.
Algorithm — multi-source frontier expansion
- Scan once: enqueue every rotten orange and count every fresh orange.
- Early exit: if there are no fresh oranges, return
0. - BFS layer: process exactly the current queue size — those oranges rot neighbors during this minute.
- When a fresh neighbor rots: mark it rotten immediately, decrement
fresh, and enqueue it for the next minute. - Finish: if
fresh == 0, return the minutes used; otherwise return-1.
🎯 When to recognize this pattern:
- A process spreads from many starting points and you need the minimum time, distance, or number of layers.
- Signal words are “simultaneously”, “minutes”, “nearest source”, or “spread to neighbors”.
- Related problems: LC 286 Walls and Gates, LC 542 01 Matrix, LC 1162 As Far from Land as Possible.
Why level-order matters:
- Every node currently in the queue was infected in the previous minute, so all of them infect neighbors during the current minute.
- Incrementing time per BFS layer — not per orange — is what makes the answer match real elapsed minutes.
04
Section Four · Walkthrough
Visual Walkthrough
Rotting Oranges — one BFS layer per minute
05
Section Five · Code
Code — Java & Python
Java — multi-source BFS
import java.util.ArrayDeque;
import java.util.Queue;
class Solution {
public int orangesRotting(int[][] grid) {
int rows = grid.length, cols = grid[0].length;
Queue<int[]> queue = new ArrayDeque<>();
int fresh = 0;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] == 2) queue.offer(new int[] { r, c });
if (grid[r][c] == 1) fresh++;
}
}
if (fresh == 0) return 0;
int minutes = 0;
int[][] dirs = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
while (!queue.isEmpty() && fresh > 0) {
int size = queue.size();
minutes++;
for (int i = 0; i < size; i++) {
int[] cell = queue.poll();
for (int[] dir : dirs) {
int nr = cell[0] + dir[0];
int nc = cell[1] + dir[1];
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
if (grid[nr][nc] != 1) continue;
grid[nr][nc] = 2; // mark on enqueue — prevents duplicates
fresh--;
queue.offer(new int[] { nr, nc });
}
}
}
return fresh == 0 ? minutes : -1;
}
}
Python — multi-source BFS
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):
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
minutes = 0
dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
while queue and fresh > 0:
for _ in range(len(queue)):
r, c = queue.popleft()
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if nr < 0 or nr >= rows or nc < 0 or nc >= cols:
continue if grid[nr][nc] != 1:
continue
grid[nr][nc] = 2
fresh -= 1
queue.append((nr, nc))
minutes += 1 return minutes if fresh == 0 else -1
06
Section Six · Analysis
Complexity Analysis
| Approach | Time | Space | Trade-off |
|---|---|---|---|
| Minute-by-minute rescan | O((m · n)²) | O(m · n) | Easy to reason about, but it repeatedly rechecks unchanged cells. |
| Per-orange repeated search | O((m · n)²) | O(m · n) | Also finds reachability, but duplicates work across many infection paths. |
| Multi-source BFS ← optimal | O(m · n) | O(m · n) | Each orange enters the queue at most once, and each edge check is constant work. |
Why not DFS?:
- DFS can tell you which fresh oranges are reachable from one rotten source, but the problem asks for the minimum number of minutes when many sources spread simultaneously.
- BFS layers match time directly, which removes the need for manual distance bookkeeping.
07
Section Seven · Edge Cases
Edge Cases & Pitfalls
| Case | What should happen | Why it matters |
|---|---|---|
| No fresh oranges anywhere | Return 0 | No time is needed if the grid is already stable. |
| Fresh orange blocked by empty cells | Return -1 | Reachability matters more than the number of rotten sources. |
| Multiple rotten oranges initially | Enqueue all of them at minute 0 | This is what makes the answer minimum rather than source-dependent. |
| Single-cell grid | [[0]] → 0, [[1]] → -1, [[2]] → 0 | Boundary cases expose missing early returns. |
| Large connected region | Still O(m·n) | Each orange rots once; repeated scans would waste work here. |
⚠ Common Mistake: Incrementing
minutes for every orange processed instead of every BFS layer gives answers that are far too large. Another off-by-one bug is incrementing after the last layer even when no fresh oranges remain. Using while (!queue.isEmpty() && fresh > 0) keeps the minute counter honest.