Rotting Oranges — Solution

Problem

Given a grid where each cell holds either an empty space (0), a fresh orange (1), or a rotten orange (2), simulate the spread of rot: every minute, any fresh orange 4-directionally adjacent to a rotten one also becomes rotten. Return the minimum number of minutes until no fresh oranges remain, or -1 if that is impossible.

• Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
• Output: 4
• Explanation: rot spreads outward from (0,0) each minute, reaching the bottom-right corner at minute 4

Counter-example showing the impossible case:

• Input: the grid above
• Output: -1
• Explanation: the middle column of fresh oranges cannot be reached because row 1 has no path from the rotten orange

Intuition

All rotten oranges spread simultaneously — this is a multi-source BFS problem where every initially rotten orange is a starting node. Each BFS level naturally corresponds to one minute of spreading. Seeding the queue with all rotten oranges at once and processing level by level automatically models the parallel infection without simulating minute by minute.

Solution — Multi-Source BFS

Enqueue every initially rotten orange, then drain the queue level by level, where each full level represents one minute passing.

1. Scan the grid: enqueue every cell where grid[r][c] == 2, count cells where grid[r][c] == 1.
2. If fresh_count == 0, return 0 immediately — no spreading needed.
3. Process the queue level by level; for each dequeued cell, check all four neighbors.
4. If a neighbor is fresh, mark it rotten (so it won't be re-enqueued), decrement fresh_count, and enqueue it.
5. After processing a full level, increment the minute counter.
6. When the queue empties, return minutes - 1 if fresh_count == 0, else -1.

The - 1 corrects for the final BFS level that dequeues the last batch of newly-rotten oranges but infects nothing new, adding a phantom extra minute.

1from collections import deque
2
3def orangesRotting(grid: list[list[int]]) -> int:
4    rows, cols = len(grid), len(grid[0])
5    queue = deque()
6    fresh_count = 0
7
8    for r in range(rows):
9        for c in range(cols):
10            if grid[r][c] == 2:
11                queue.append((r, c))
12            elif grid[r][c] == 1:
13                fresh_count += 1
14
15    if fresh_count == 0:
16        return 0
17
18    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
19    minutes = 0
20
21    while queue:
22        for _ in range(len(queue)):  # snapshot level size before the loop adds new entries
23            row, col = queue.popleft()
24            for dr, dc in directions:
25                new_row, new_col = row + dr, col + dc
26                if 0 <= new_row < rows and 0 <= new_col < cols and grid[new_row][new_col] == 1:
27                    grid[new_row][new_col] = 2  # mark rotten on enqueue so neighbors skip it
28                    fresh_count -= 1
29                    queue.append((new_row, new_col))
30        minutes += 1
31
32    return minutes - 1 if fresh_count == 0 else -1

Time: O(m × n) — each cell is enqueued and dequeued at most once.

Space: O(m × n) — the queue holds at most every cell in the worst case where all oranges are initially rotten.

Complexity Summary

Common Mistakes

• Single-source BFS: Seeding the queue with only one rotten orange — all rotten oranges spread in parallel, so you must enqueue every rotten cell upfront or you'll miscount the elapsed time.
• Marking cells rotten on dequeue instead of enqueue: A fresh orange adjacent to two rotten neighbors gets enqueued twice; marking it 2 only when you pop it means it enters the queue twice, corrupting fresh_count (decremented twice for the same orange).
• Off-by-one on the minutes counter: Returning minutes instead of minutes - 1 — the last BFS level processes newly-rotten cells that infect nothing new, causing the counter to overshoot by one.
• Forgetting the impossible-case check: Returning minutes - 1 unconditionally — fresh oranges blocked by empty cells (0s) never get infected; only checking fresh_count > 0 after BFS reveals these unreachable oranges.
• Using DFS instead of BFS: DFS explores depth-first and does not process cells in distance order, so it cannot determine the minimum number of minutes — BFS levels directly model the simultaneous per-minute spreading.

Related Problems

• 01 Matrix — multi-source BFS from all 0-cells simultaneously to compute shortest distance to the nearest 0, the same pattern as spreading from all rotten oranges
• Flood Fill — BFS/DFS spreading from a single source cell through a connected grid region
• Number of Islands — BFS/DFS to explore and count connected components in a grid
• Max Area of Island — BFS/DFS on a grid that accumulates cell count per connected component
• Word Ladder — BFS counting minimum transformation levels, the same level-by-level counting pattern as minutes in this problem