Rotting Oranges

Rotting Oranges is the classic introduction to multi-source BFS — a breadth-first search that starts from many sources at once and spreads outward in lockstep. It is the go-to pattern whenever something diffuses across a grid one step per "tick."

The slow way first

You could re-scan the whole grid every minute: walk every cell, and for each rotten one mark its fresh neighbours, repeating until a full pass changes nothing. That works but it is clumsy — each minute costs a full O(rows·cols) sweep, and you have to carefully avoid rotting a cell twice in the same minute.

The cleaner question: the rot spreads outward in waves, one ring per minute — what data structure processes a graph in waves? A queue (BFS).

The idea: spread from all sources at once

A normal BFS starts from one node. Here the rot starts from every rotten orange simultaneously, so we seed the queue with all of them before we start. Then each "minute" is exactly one BFS layer: pop everything currently in the queue, rot their fresh neighbours, and push those neighbours for the next minute.

We also count the fresh oranges up front. Every time we rot one we decrement that count; if it hits 0, everything rotted. If the queue empties while fresh is still positive, those oranges were unreachable and we return -1.

The key insight: processing the queue one layer at a time (a for _ in range(len(q)) over the current size) is what turns BFS distance into minutes.

Walk through it

Step through the animation. The dark cell at the top-left is the only rotten orange, so it alone seeds the queue. Minute 1 rots its two neighbours; minute 2 those rot the next ring; and the wave keeps spreading until minute 4, when the last fresh orange at the bottom-right finally rots. The fresh counter ticks down to 0, so we return 4.

Pseudocode

queue = all cells that start rotten
fresh = count of cells that start fresh
minutes = 0
while queue is not empty and fresh > 0:
    minutes += 1
    for each cell currently in the queue (one full layer):
        pop it
        for each 4-directional neighbour:
            if the neighbour is fresh:
                make it rotten
                fresh -= 1
                push it onto the queue
return minutes if fresh == 0 else -1

The Python solution

from collections import deque
 
def oranges_rotting(grid):
    rows, cols = len(grid), len(grid[0])
    q = deque()
    fresh = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                q.append((r, c))
            elif grid[r][c] == 1:
                fresh += 1
    minutes = 0
    dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    while q and fresh > 0:
        minutes += 1
        for _ in range(len(q)):
            r, c = q.popleft()
            for dr, dc in dirs:
                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
                    q.append((nr, nc))
    return minutes if fresh == 0 else -1

• The first double loop seeds the queue with every rotten orange and counts the fresh ones — this is what makes it multi-source.
• while q and fresh > 0 stops as soon as everything rots, so we never add an extra empty minute.
• for _ in range(len(q)) snapshots the current layer size before we start popping, so each pass processes exactly one minute's worth of oranges.
• We only spread into cells equal to 1 (fresh), and we flip them to 2 immediately — that doubles as the "visited" mark, so no cell is ever queued twice.
• At the end, fresh == 0 means full coverage; otherwise some orange was walled off and we return -1.

Complexity

Every cell is visited and enqueued at most once, so the whole algorithm is linear in the grid size. The space is the queue, which in the worst case holds a full layer of the grid.

When this pattern shows up

Practice