Rotten Oranges
Rotten oranges rot their 4-neighbours each minute. Return minutes until all rot, or −1 if some never do.
Open on LeetCode ↗02
Intuition
Rot spreads like a wave from every rotten orange at once — that's a multi-source BFS. Seed the queue with all initially rotten cells; each BFS layer is one minute. Fresh oranges the wave never reaches → −1.
03
Approach
1
Seed all sources at once
Push every rotten cell with time 0 and count the fresh ones. Multi-source BFS is just BFS with many starting points.
2
Layer = minute
Process the queue; a fresh neighbour rots at parent time + 1. BFS guarantees each orange is reached at its earliest possible minute.
3
Check completeness
If fresh count hits 0, the last rot time is the answer; otherwise some orange was unreachable → −1.
04
Solution & live demo
python
▶1from collections import deque
▶2
▶3class Solution:
▶4 def orangesRotting(self, grid):
▶5 R, C = len(grid), len(grid[0])
▶6 q, fresh = deque(), 0
▶7 for r in range(R):
▶8 for c in range(C):
▶9 if grid[r][c] == 2: q.append((r, c, 0))
▶10 elif grid[r][c] == 1: fresh += 1
▶11 t = 0
▶12 while q:
▶13 r, c, t = q.popleft()
▶14 for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
▶15 nr, nc = r + dr, c + dc
▶16 if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] == 1:
▶17 grid[nr][nc] = 2
▶18 fresh -= 1
▶19 q.append((nr, nc, t + 1))
▶20 return t if fresh == 0 else -1
05
Edge cases
No fresh oranges at start
Answer 0 — nothing to wait for.
Fresh orange walled off by empties
Never enqueued; fresh count stays positive → −1.
06
Complexity
Time
O(R·C)
Space
O(R·C)
Each cell enqueued at most once.