How many minutes until every orange rots? Start a breadth-first search from all the rotten ones at once, one ring per minute.
▼The problem
LeetCode 994 (Medium). A grid holds 0 (empty), 1 (a fresh orange) or 2 (a rotten orange). Every minute, each rotten orange rots the fresh oranges next to it (up, down, left, right). Return the minutes until no fresh orange is left, or -1 if that can never happen.
Examples: [[2,1,1],[1,1,0],[0,1,1]] → 4 (the rot reaches (1,0),(0,1), then (1,1),(0,2), then (2,1), then (2,2)); [[2,1,1],[0,1,1],[1,0,1]] → -1 (the orange at (2,0) is walled off by empty cells).
The solution
from collections import deque
def orangesRotting(grid):
m, n = len(grid), len(grid[0])
q = deque((r, c) for r in range(m) for c in range(n) if grid[r][c] == 2)
fresh = sum(row.count(1) for row in grid)
minutes = 0
while q and fresh:
for _ in range(len(q)): # one level
r, c = q.popleft()
for nr, nc in (r+1, c), (r-1, c), (r, c+1), (r, c-1):
if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:
grid[nr][nc] = 2 # rot it
fresh -= 1
q.append((nr, nc))
minutes += 1
return minutes if fresh == 0 else -1Transcript
Rotting Oranges. Each cell of a grid is empty, a fresh orange, or a rotten one. Every minute, rotten oranges spoil their fresh neighbours: up, down, left and right. How many minutes until none are fresh? If some never rot, return minus one.
In this crate, the rot spreads in waves, and after four minutes the last orange turns: the answer is four. But here, one orange is walled off by empty cells. It never rots, so the answer is minus one.
The slow way scans the whole grid every minute, spoiling neighbours, until nothing changes. There can be as many minutes as cells, so the work grows with the square of the grid.
Instead, run a breadth first search from every rotten orange at once. Queue them all at minute zero. Each level of the queue is one minute: pop its oranges, and push the fresh neighbours they spoil. Count the fresh ones too, to spot any left behind.
In code, queue the rotten, count the fresh. While both remain, process one level: check four neighbours, rot each fresh one, lower the count, and queue it. Then add a minute. Return the minutes if nothing is fresh, else minus one.
Back to our crate. Minute zero: one rotten, six fresh. Minute one: two rot, four left. Minute two: two more, two left. Minute three: one left. Minute four: zero. Four minutes.
Each cell joins the queue once and checks four neighbours, so time is order m times n, and so is the space.
Start every rot at once, and count the waves. That's Rotting Oranges.