Rotting Oranges: Multi-Source BFS on a Grid

"Rotting Oranges" is a Medium-level staple in Amazon, Google, Microsoft loops, and it is a textbook fit for the Tree BFS pattern — one of the nine patterns that cover the bulk of what FAANG coding interviews actually test. Part 9 of 11 in the Tree BFS arc.

The Problem

In a grid of empty cells (0), fresh oranges (1), and rotten oranges (2), rot spreads to 4-directionally adjacent fresh oranges every minute. Return the minutes until no fresh orange remains, or -1 if some can never rot. The go-to question for multi-source BFS.

Input:  grid = [[2, 1, 1], [1, 1, 0], [0, 1, 1]]
Output: 4

Recognizing the Tree BFS Pattern

Breadth-first search explores a tree or graph level by level using a queue, and its defining superpower is the level snapshot: freeze the queue length, process exactly that many nodes, and you have processed one complete level. Anything phrased per-level — level lists, level averages, rightmost visible node, shortest path in unweighted structures — is BFS by construction.

Simultaneous spread from many origins in unit time steps is BFS with all sources enqueued at minute zero — the level structure then equals elapsed time. Running one BFS per source and combining is both wrong and slow; the single-queue seeding is the pattern.

The Approach

Scan once: enqueue every rotten cell, count fresh ones. Then level-snapshot BFS: each round rots the fresh neighbors of the current frontier, decrementing the fresh count, incrementing the clock per non-empty round. Finish: fresh count zero gives the clock; anything left gives -1.

Mark cells rotten at enqueue time, not at pop time — deferring the mark lets two frontier cells enqueue the same orange twice. That double-enqueue bug is the grid-BFS classic.

Python Solution

from collections import deque


def oranges_rotting(grid: list[list[int]]) -> int:
    """Minutes for rot to reach every fresh orange, else -1."""
    rows, cols = len(grid), len(grid[0])
    queue: deque[tuple[int, int]] = 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:
        minutes += 1
        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       # mark at enqueue time
                    fresh -= 1
                    queue.append((nr, nc))
    return minutes if fresh == 0 else -1

Complexity

• Time: O(m·n) — each cell is enqueued at most once
• Space: O(m·n) — queue worst case; rot marks reuse the grid

Interview Tips and Follow-Ups

• The while queue and fresh guard prevents counting a final round that rots nothing — the standard off-by-one-minute bug.
• Walls and Gates and 01 Matrix are the same multi-source template — distance-from-nearest-source problems, all of them.
• If mutation of the input grid is off-limits, say you would copy it or keep a visited set, and what that costs.

More Tree BFS problems — and the other eight patterns — live in the Technical Interview category. Drill the pattern, not the problem: that is the entire thesis of this series.