TL;DR
Simultaneous spread from all rotten oranges = multi-source BFS, where each level is one minute — O(m·n) time, O(m·n) space.
Approach 1 — Brute force (repeated full-grid passes)
The insight: simulate minute by minute. Each minute, scan the whole grid, find every fresh orange next to a rotten one, and rot them — but only after the scan, so oranges rotted this minute don’t chain-rot in the same minute. Repeat until a full pass changes nothing.
class Solution:
def orangesRotting(self, grid: list[list[int]]) -> int:
m, n = len(grid), len(grid[0])
minutes = 0
while True:
to_rot = []
for r in range(m):
for c in range(n):
if grid[r][c] == 2:
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:
to_rot.append((nr, nc))
if not to_rot:
break
for r, c in to_rot:
grid[r][c] = 2
minutes += 1
if any(cell == 1 for row in grid for cell in row):
return -1
return minutes
Complexity: each minute rescans all m·n cells, and there can be O(m·n) minutes → O((m·n)²) time. Fine for the 10×10 limit, but BFS does it in one pass.
Approach 2 — Multi-source BFS (optimal)
The insight: the rot front expands uniformly one ring per minute — exactly the level structure of BFS. Seed the queue with all rotten oranges at time 0 (multi-source), process the queue one full level at a time, and each completed level with new infections is one elapsed minute. Track the fresh count so you can both stop early and detect unreachable oranges.
from collections import deque
class Solution:
def orangesRotting(self, grid: list[list[int]]) -> int:
m, n = len(grid), len(grid[0])
queue = deque()
fresh = 0
for r in range(m):
for c in range(n):
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)): # drain exactly one minute's front
r, c = queue.popleft()
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:
grid[nr][nc] = 2 # rot it now (marks visited)
fresh -= 1
queue.append((nr, nc))
return minutes if fresh == 0 else -1
Walkthrough (grid = [[2,1,1],[1,1,0],[0,1,1]]): fresh = 6, queue = [(0,0)]. Minute 1: (0,0) rots (0,1) and (1,0), fresh→4. Minute 2: (0,1)→(0,2), (1,0)→(1,1), fresh→2. Minute 3: (0,2) has no fresh neighbor, (1,1)→(2,1), fresh→1. Minute 4: (2,1)→(2,2), fresh→0. Loop ends, fresh == 0 → return 4.
Complexity: every cell is enqueued at most once and its 4 neighbors scanned once → O(m·n) time, O(m·n) space for the queue.
Common pitfalls
- Not fixing the level size. Loop
for _ in range(len(queue)) to process exactly the oranges present at the start of the minute; reading len(queue) inside the loop after appending merges future minutes into the current one and undercounts time.
- The all-empty / no-fresh case. If
fresh == 0 at the start, the answer is 0 — don’t return a minute count from a loop that ran zero times inconsistently.
- Forgetting the
-1 check. Fresh oranges walled off by empty cells never rot; after BFS, any remaining fresh means return -1.
- Off-by-one on minutes. Increment the minute counter before draining a level so the count equals the number of spreading rounds, then trust
fresh == 0 to validate.
Pattern takeaway
When a process spreads from many sources at once and you need the time/steps for full coverage, use multi-source BFS: enqueue every source at level 0 and count levels. Prefer BFS over DFS whenever the answer is a shortest time or fewest steps — BFS’s level structure is the clock. Pair it with a running “remaining” count to stop early and to detect unreachable targets.