Rotting Oranges
Spread rot one minute at a time — the problem that shows why BFS, not DFS, answers questions about time and distance
Problem Statement
A grid holds 0 (empty), 1 (fresh orange) and 2 (rotten orange). Every minute, any fresh orange touching a rotten one on an edge becomes rotten.
Return the minutes until no fresh orange remains, or -1 if that never happens.
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 bottom-left 1 is cut off — nothing ever reaches itIntuition
Two things make this different from Flood Fill, and both point at BFS.
It asks about time. Not "which oranges rot" but "how long". Time here means number of steps from a rotten orange — which is distance. BFS is the traversal that arrives in distance order; DFS is not.
Rot starts everywhere at once. There may be several rotten oranges, and they all spread simultaneously. This is a multi-source BFS.
The insight
Put every rotten orange in the queue before starting.
BFS then expands from all of them together, in lockstep. Each orange is reached by whichever source is nearest, which is exactly what "they spread at the same time" means.
Running BFS once per rotten orange and taking the minimum would give the same answer at many times the cost. Seeding the queue with all starting points is the trick worth remembering.
Then process the queue one level at a time. Each level is one minute.
Approach
Scan the grid once
Queue every rotten orange. Count the fresh ones — that counter is how you detect the unreachable case at the end.
If there are no fresh oranges, return 0
Nothing needs to happen. This must be checked before the loop, or the level counting reports 1 minute too many.
BFS, processing a whole level per iteration
Record the queue's size before the inner loop, and process exactly that many. Everything added during it belongs to the next minute.
Solution
from collections import deque
def oranges_rotting(grid: list[list[int]]) -> int:
"""Minutes until no fresh orange remains, or -1 if impossible."""
rows, cols = len(grid), len(grid[0])
queue: deque[tuple[int, int]] = deque()
fresh = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == 2:
queue.append((r, c)) # every source, queued up front
elif grid[r][c] == 1:
fresh += 1
if fresh == 0:
return 0
minutes = 0
directions = ((-1, 0), (1, 0), (0, -1), (0, 1))
while queue and fresh > 0:
# Everything currently queued rots in the SAME minute.
for _ in range(len(queue)):
r, c = queue.popleft()
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
grid[nr][nc] = 2
fresh -= 1
queue.append((nr, nc))
minutes += 1
return minutes if fresh == 0 else -1for _ in range(len(queue)) captures the size before the loop begins. Iterating the queue directly while appending to it would merge every minute into one.
Complexity Analysis
Time Complexity
O(rows × cols)
Space Complexity
O(rows × cols)
Time — one scan to seed, then each orange enters and leaves the queue at most once, checking four neighbours.
Space — the queue. In the worst case every cell is rotten at the start and all of them are queued together.
Edge Cases
Related Problems
- Flood Fill — the same grid traversal when order does not matter
- Number of Islands — counting regions instead of measuring distance
- Binary Tree Level Order Traversal — the same level-size trick, on a tree