136. Rotting Oranges

Why this mechanism works

All initial rotten cells are distance-zero sources. A multi-source BFS discovers each fresh orange at its earliest possible infection time. Track the remaining fresh count separately: a finished queue does not prove success when isolated fresh cells remain.

State and boundaries

queue stores rotten cells with their infection minute. fresh counts undiscovered fresh oranges; minutes is the latest processed infection time.

Protocol

1. Seed every rotten cell at time zero and count fresh cells.
2. Pop in FIFO order.
3. Recolor each fresh neighbor to rotten before enqueueing it at time+1.
4. Decrement fresh once per discovery.
5. Return minutes only if fresh becomes zero.

Visualization

all initial rotten cells: time 0
their fresh neighbors: time 1
next frontier: time 2
answer is last infection time, not visited count

Python implementation

from collections import deque

def rotting_oranges(grid):
    rows = len(grid)
    cols = len(grid[0]) if rows else 0
    queue = deque()
    fresh = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c, 0))
            elif grid[r][c] == 1:
                fresh += 1
    minutes = 0
    while queue:
        r, c, time = queue.popleft()
        minutes = max(minutes, time)
        for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
            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, time + 1))
    return minutes if fresh == 0 else -1

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L4 rotting_oranges: rows = len(grid)
grid=[[2, 1, 1], [1, 1, 0], [0, 1, 1]]; rows=3

L5 rotting_oranges: cols = len(grid[0]) if rows else 0
grid=[[2, 1, 1], [1, 1, 0], [0, 1, 1]]; rows=3; cols=3

L6 rotting_oranges: queue = deque()
grid=[[2, 1, 1], [1, 1, 0], [0, 1, 1]]; rows=3; cols=3; queue=deque([])

L7 rotting_oranges: fresh = 0
grid=[[2, 1, 1], [1, 1, 0], [0, 1, 1]]; rows=3; cols=3; queue=deque([]); fresh=0

L8 rotting_oranges: for r in range(rows):
grid=[[2, 1, 1], [1, 1, 0], [0, 1, 1]]; rows=3; cols=3; queue=deque([]); fresh=0; r=0

L9 rotting_oranges: for c in range(cols):
grid=[[2, 1, 1], [1, 1, 0], [0, 1, 1]]; rows=3; cols=3; queue=deque([]); fresh=0; r=0; c=0

L11 rotting_oranges: queue.append((r, c, 0))
grid=[[2, 1, 1], [1, 1, 0], [0, 1, 1]]; rows=3; cols=3; queue=deque([(0, 0, 0)]); fresh=0; r=0; c=0

L9 rotting_oranges: for c in range(cols):
grid=[[2, 1, 1], [1, 1, 0], [0, 1, 1]]; rows=3; cols=3; queue=deque([(0, 0, 0)]); fresh=0; r=0; c=1

... 97 intermediate state changes omitted ...

L18 rotting_oranges: for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
grid=[[2, 2, 2], [2, 2, 0], [0, 2, 2]]; rows=3; cols=3; queue=deque([]); fresh=0; r=2; c=2; minutes=4; time=4; dr=0; dc=1; nr=1; nc=2

L19 rotting_oranges: nr, nc = r + dr, c + dc
grid=[[2, 2, 2], [2, 2, 0], [0, 2, 2]]; rows=3; cols=3; queue=deque([]); fresh=0; r=2; c=2; minutes=4; time=4; dr=0; dc=1; nr=2; nc=3

L18 rotting_oranges: for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
grid=[[2, 2, 2], [2, 2, 0], [0, 2, 2]]; rows=3; cols=3; queue=deque([]); fresh=0; r=2; c=2; minutes=4; time=4; dr=0; dc=-1; nr=2; nc=3

L19 rotting_oranges: nr, nc = r + dr, c + dc
grid=[[2, 2, 2], [2, 2, 0], [0, 2, 2]]; rows=3; cols=3; queue=deque([]); fresh=0; r=2; c=2; minutes=4; time=4; dr=0; dc=-1; nr=2; nc=1

L4 rotting_oranges: rows = len(grid)
grid=[[2, 0, 1]]; rows=1

L5 rotting_oranges: cols = len(grid[0]) if rows else 0
grid=[[2, 0, 1]]; rows=1; cols=3

L6 rotting_oranges: queue = deque()
grid=[[2, 0, 1]]; rows=1; cols=3; queue=deque([])

L7 rotting_oranges: fresh = 0
grid=[[2, 0, 1]]; rows=1; cols=3; queue=deque([]); fresh=0

L8 rotting_oranges: for r in range(rows):
grid=[[2, 0, 1]]; rows=1; cols=3; queue=deque([]); fresh=0; r=0

L9 rotting_oranges: for c in range(cols):
grid=[[2, 0, 1]]; rows=1; cols=3; queue=deque([]); fresh=0; r=0; c=0

L11 rotting_oranges: queue.append((r, c, 0))
grid=[[2, 0, 1]]; rows=1; cols=3; queue=deque([(0, 0, 0)]); fresh=0; r=0; c=0

L9 rotting_oranges: for c in range(cols):
grid=[[2, 0, 1]]; rows=1; cols=3; queue=deque([(0, 0, 0)]); fresh=0; r=0; c=1

... 8 intermediate state changes omitted ...

L18 rotting_oranges: for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
grid=[[2, 0, 1]]; rows=1; cols=3; queue=deque([]); fresh=1; r=0; c=0; minutes=0; time=0; dr=0; dc=1; nr=-1; nc=0

L19 rotting_oranges: nr, nc = r + dr, c + dc
grid=[[2, 0, 1]]; rows=1; cols=3; queue=deque([]); fresh=1; r=0; c=0; minutes=0; time=0; dr=0; dc=1; nr=0; nc=1

L18 rotting_oranges: for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
grid=[[2, 0, 1]]; rows=1; cols=3; queue=deque([]); fresh=1; r=0; c=0; minutes=0; time=0; dr=0; dc=-1; nr=0; nc=1

L19 rotting_oranges: nr, nc = r + dr, c + dc
grid=[[2, 0, 1]]; rows=1; cols=3; queue=deque([]); fresh=1; r=0; c=0; minutes=0; time=0; dr=0; dc=-1; nr=0; nc=-1

Why the solution is correct

BFS processes infection layers in increasing time, so the first discovery gives each reachable orange its minimum infection time. The maximum such time is when all reachable fresh oranges have rotted. A positive remaining fresh count identifies exactly the unreachable ones.

Time and space

O(R*C) time and O(R*C) queue space.

Common mistakes

Starting from only one rotten orange ignores parallel spread. Counting one minute per popped cell confuses cells with BFS layers.

Reasoning card

Transfer exercise

Assign different nonnegative transmission times to edges and explain why FIFO BFS must become a weighted shortest-path algorithm.