Rotting Oranges — Multi-Source BFS Pattern Every FAANG Interviewer Loves

Problem Statement#

You are given an m x n grid where each cell contains one of three values:

• 0 representing an empty cell.
• 1 representing a fresh orange.
• 2 representing a rotten orange.

Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten. Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.

Constraints:

• 1 <= m, n <= 10
• grid[i][j] is 0, 1, or 2.

Input:  grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4
Explanation: After 4 minutes, all reachable fresh oranges become rotten.

Input:  grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The fresh orange at the bottom-left is unreachable.

Input:  grid = [[0,2]]
Output: 0
Explanation: There are no fresh oranges, so the answer is 0.

Why This Problem Matters#

LeetCode 994 Rotting Oranges is one of the most asked grid BFS problems at FAANG, especially at Amazon, Google, and Microsoft. It is the canonical example of multi-source BFS — a pattern where multiple starting points expand simultaneously level by level.

This pattern shows up in production systems all the time:

• Network propagation: how fast does a packet flood reach every router?
• Disease spread simulations: epidemiological SIR models on a contact graph.
• Fire / water spread: shortest distance from any "infected" cell to all others.
• Distributed cache invalidation: when many caches go stale at once.

If you can solve Rotting Oranges, you can solve Walls and Gates, 01 Matrix, Shortest Bridge, As Far From Land As Possible, and many more. It is the gateway problem to BFS mastery.

The Core Insight#

A naive single-source BFS — pick one rotten orange, spread, then repeat for the next — gives the wrong answer. Why? Because in this problem all rotten oranges spread simultaneously, not sequentially. The minute counter is global, not per-source.

The trick is multi-source BFS: enqueue every initially rotten orange together at time 0, then run a single BFS. Each BFS level corresponds to one minute. After processing all reachable cells, if any fresh orange remains, return -1.

Two equivalent ways to track minutes:

1. Per-cell timestamp: store (row, col, minute) in the queue and let the maximum minute be the answer.
2. Level-by-level loop: process the queue in chunks of len(queue) per minute, incrementing a counter each level.

Both are correct. The level-by-level form is what interviewers usually prefer because it makes "minutes" explicit.

Visual Dry Run#

Input grid:

2 1 1
1 1 0
0 1 1

Fresh oranges = 6. Initial queue = [(0,0)] (one rotten orange). Minutes = 0.

Fresh remaining = 0. Answer = 4.

Note how minute 2 rots two cells simultaneously — that is the multi-source magic. A single-source BFS would rot them on different minutes.

Solution (Optimal)#

# Python — multi-source BFS, O(m*n) time, O(m*n) space
from collections import deque
 
def orangesRotting(grid: list[list[int]]) -> int:
    m, n = len(grid), len(grid[0])
    queue = deque()
    fresh = 0
 
    # Step 1: enqueue every rotten orange and count fresh oranges
    for r in range(m):
        for c in range(n):
            if grid[r][c] == 2:
                queue.append((r, c))
            elif grid[r][c] == 1:
                fresh += 1
 
    if fresh == 0:
        return 0
 
    minutes = 0
    dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
 
    # Step 2: BFS level by level, each level = one minute
    while queue and fresh > 0:
        for _ in range(len(queue)):
            r, c = queue.popleft()
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    fresh -= 1
                    queue.append((nr, nc))
        minutes += 1
 
    return minutes if fresh == 0 else -1

// JavaScript — multi-source BFS, O(m*n) time, O(m*n) space
function orangesRotting(grid) {
    const m = grid.length, n = grid[0].length;
    const queue = [];
    let fresh = 0;
 
    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            if (grid[r][c] === 2) queue.push([r, c]);
            else if (grid[r][c] === 1) fresh++;
        }
    }
 
    if (fresh === 0) return 0;
 
    let minutes = 0;
    const dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]];
 
    while (queue.length && fresh > 0) {
        const size = queue.length;
        for (let i = 0; i < size; i++) {
            const [r, c] = queue.shift();
            for (const [dr, dc] of dirs) {
                const nr = r + dr, nc = c + dc;
                if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] === 1) {
                    grid[nr][nc] = 2;
                    fresh--;
                    queue.push([nr, nc]);
                }
            }
        }
        minutes++;
    }
 
    return fresh === 0 ? minutes : -1;
}

Complexity:

Common Mistakes#

1. Counting minutes when there are no fresh oranges. If fresh == 0 initially, return 0 immediately. Many candidates return -1 or some accidental count.

2. Incrementing minutes even when no new oranges rotted on the last level. If you increment unconditionally inside the outer loop without checking that the level actually rotted something, you over-count by one. Either guard with fresh > 0 (as above) or only increment when at least one neighbor was infected this round.

3. Single-source BFS bug. Running BFS from one rotten orange at a time produces incorrect timing because subsequent BFS calls would have started after the first source already rotted everything reachable.

4. Mutating the grid vs. using a visited set. Both work, but if the interviewer says "do not mutate the input," use a visited set. Otherwise mutating to 2 keeps space at O(queue_size).

5. Forgetting to validate fresh == 0 at the end. Some fresh oranges may be unreachable (walled off by 0s). The answer is -1 in that case, not minutes.

Interview Tips#

• Start by saying out loud: "All rotten oranges spread at the same time, so this is multi-source BFS, not flood fill from one cell."
• Ask: "Can the grid be empty? Can it have only fresh oranges? Only rotten? Are diagonal neighbors infectious?" These show you check edge cases before coding.
• When discussing complexity, emphasize O(m*n) — every cell is enqueued and dequeued at most once. This is optimal because we must inspect every cell.
• If the interviewer ramps up: "What if the grid is huge and rotten oranges are sparse?" Suggest bidirectional BFS or A* — but for this problem, plain BFS is optimal.

Follow-up Questions#

1. Diagonal infection (8 directions). Just expand dirs to include the four diagonals.
2. Different infection speeds. If oranges rot every k minutes instead of every minute, multiply minutes by k or use Dijkstra.
3. Multiple infection types. If two viruses spread, run two simultaneous BFS frontiers and resolve conflicts by precedence.
4. Walls and Gates (LC 286). Same multi-source BFS but for distance-to-nearest-gate.
5. 01 Matrix (LC 542). Same pattern: BFS from every 0 to fill nearest-zero distance for every 1.

Key Takeaways#

• Multi-source BFS is the optimal pattern for "infection spreads simultaneously from many sources" problems — enqueue every source at minute zero before starting the BFS loop.
• Each BFS level corresponds to one minute; process the queue in fixed-size chunks (for _ in range(len(queue))) to count levels cleanly.
• Track a fresh counter so you can return -1 when some oranges are unreachable.
• Time and space are both O(m*n) because every cell is visited at most once.
• The same pattern unlocks LC 286 Walls and Gates, LC 542 01 Matrix, LC 1162 As Far From Land, and LC 934 Shortest Bridge — learn it once, solve many.
• Interviewers love this problem because it tests whether you recognize that "simultaneous spread" implies multi-source BFS, not repeated single-source BFS.