Rotting Oranges

Signal

"Everything spreads outward simultaneously, minute by minute" is multi-source BFS with a time dimension — seed the queue with every starting rotten orange at once, and each BFS layer corresponds to exactly one elapsed minute.

Approach

Push every initially-rotten orange into the queue up front and count the fresh oranges. Run BFS level by level; each level (all nodes currently in the queue before you start processing) represents one minute, and every fresh neighbor turned rotten during that level decrements the fresh count. Stop when the queue empties — the number of levels processed is the answer, unless fresh oranges remain, which means -1.

Skeleton

queue = all initially-rotten cells
fresh = count of fresh cells
minutes = 0
while queue and fresh > 0:
    for _ in range(len(queue)):  # one full level = one minute
        cell = queue.pop()
        for neighbor in adjacent(cell):
            if neighbor is fresh:
                rot it; fresh -= 1; queue.push(neighbor)
    minutes += 1
return minutes if fresh == 0 else -1

Solution

from collections import deque


def oranges_rotting(grid: list[list[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c))
            elif grid[r][c] == 1:
                fresh += 1

    minutes = 0
    while queue and fresh > 0:
        for _ in range(len(queue)):
            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 < 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 -1

Complexity

O(rows · cols) time — every cell enters the queue at most once. O(rows · cols) space for the queue in the worst case (grid is all rotten oranges initially).

Pitfalls

• Looping while queue without the for _ in range(len(queue)) inner loop processes cells one at a time instead of level-by-level, which miscounts minutes (or requires storing a per-cell minute, which is more bookkeeping than necessary).
• Incrementing minutes even on a final level that rots nothing new — since the loop condition checks fresh > 0 before starting a level, this doesn't happen here, but it's a common off-by-one in less careful versions.
• Forgetting the "already zero fresh oranges at the start" edge case — the while condition's fresh > 0 check handles it by never entering the loop, returning 0 correctly.