Rotten Oranges — Multi-Source BFS with Queue

Every minute, each rotten orange (value 2) makes its 4-directional neighbors rotten. Fresh oranges are value 1, empty cells are 0. Return the minimum minutes until no fresh orange remains, or -1 if impossible.

Key Insight — Multi-Source BFS

Instead of running BFS from each rotten orange separately, enqueue all rotten oranges at once as the starting level. Each BFS level represents one minute of spreading.

from collections import deque

def oranges_rotting(grid):
    """
    Time: O(m × n), Space: O(m × n)
    """
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0

    # Collect all rotten oranges and count fresh
    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

    if fresh == 0:
        return 0

    minutes = 0
    directions = [(0,1), (0,-1), (1,0), (-1,0)]

    while queue:
        minutes += 1
        for _ in range(len(queue)):
            r, c = queue.popleft()
            for dr, dc in directions:
                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))

        if fresh == 0:
            return minutes

    return -1  # Some fresh oranges unreachable

Trace

Grid:           Minute 0    Minute 1    Minute 2    Minute 3    Minute 4
2  1  1         R  1  1     R  R  1     R  R  R     R  R  R     R  R  R
1  1  0    →    1  1  0  →  R  1  0  →  R  R  0  →  R  R  0  →  R  R  0
0  1  1         0  1  1     0  1  1     0  R  1     0  R  R     0  R  R

Fresh: 6        Fresh: 4    Fresh: 2    Fresh: 1    Fresh: 0
Queue: [(0,0)]  +[(0,1),(1,0)] +[(0,2),(1,1)] +[(2,1)] +[(2,2)]

Answer: 4 minutes

Why Multi-Source BFS Works

Single-source BFS finds shortest distance from one node. Multi-source BFS finds shortest distance from the nearest source to every other node. By enqueuing all sources at level 0, BFS expands them simultaneously — exactly like the rot spreading from all rotten oranges at once.

Common Mistakes

1. Running BFS from each rotten orange separately — this is O(k × m × n) where k is the number of rotten oranges. Multi-source BFS is O(m × n).
2. Forgetting to check if fresh becomes 0 early — not wrong but misses optimization.
3. Off-by-one on minutes — count levels, not individual cells.
4. Modifying grid without checking — always check grid[nr][nc] == 1 before marking.

Edge Cases

• No fresh oranges — return 0
• No rotten oranges but fresh exist — return -1
• Fresh orange surrounded by empty — return -1 (unreachable)
• All rotten already — return 0
• Single cell — check if it’s fresh (return -1) or rotten/empty (return 0)

When to Use Multi-Source BFS

Whenever something spreads simultaneously from multiple starting points:

• Fire spreading in a forest
• Virus spreading in a network
• Distance to nearest source (0-1 BFS)
• Walls and Gates (distance to nearest gate)

Related Problems

• Walls and Gates (LeetCode 286) — distance to nearest gate
• Shortest Path to Get All Keys (LeetCode 864)
• As Far from Land as Possible (LeetCode 1162)
• Map of Highest Peak (LeetCode 1765)