Rotting Oranges — Multi-Source BFS for Time Spread (LC 994)

Problem Statement#

LeetCode 994 — Rotting Oranges (Medium)

You are given an m x n grid where each cell can have 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.

Example:

Input:
2 1 1
1 1 0
0 1 1
 
Output: 4
Explanation: At minute 4, every fresh orange has rotted.

Input:
2 1 1
0 1 1
1 0 1
 
Output: -1
Explanation: The orange at (2,0) is unreachable from any rotten cell.

Why This Problem Matters#

Rotting Oranges is the archetypal multi-source BFS problem. Where most BFS problems start from one source and find the shortest path to a target, this problem starts from every rotten orange simultaneously and asks "how long until the wave reaches every fresh orange?"

This is one of the most common Amazon, Google, and Meta on-site questions because it tests three skills at once: choosing BFS over DFS for shortest-path/time problems, implementing multi-source initialization, and handling the unreachable case correctly. Once you internalize this pattern, you can solve LC 542 (01 Matrix), LC 286 (Walls and Gates), LC 1162 (As Far From Land), and LC 1091 (Shortest Path in Binary Matrix) without breaking a sweat — they are all the same algorithm with different bookkeeping.

The Core Insight#

If only one orange were rotten, BFS would compute the shortest distance from that single source to every fresh orange — and the answer would be the maximum of those distances. With multiple rotten oranges, the rot spreads from all of them in parallel. Every fresh orange takes on the minimum distance to any rotten source.

The elegant trick: seed the BFS queue with every rotten orange before starting the loop. Now the standard level-by-level BFS naturally computes "minutes until a wave from the nearest source reaches this cell" for every fresh cell. The answer is the depth of the BFS tree (the level at which the last fresh orange was rotted).

To detect the impossible case, count fresh oranges initially. After BFS, if any remain fresh, return -1.

Why level-order BFS, not distance counts on each cell? Both work. Level-order BFS (drain the queue one level at a time, increment minutes once per level) tracks total time naturally without storing distance per cell. It also lets you exit early once no fresh oranges remain.

Visual Dry Run#

Initial grid:

2 1 1
1 1 0
0 1 1

Fresh count = 6. Queue starts with [(0,0)] (the only rotten orange).

Total minutes = 4. Fresh remaining = 0, so return 4.

For the unreachable case, the cell (2, 0) would never be reached and fresh > 0 after BFS terminates, so we return -1.

Solution (Optimal)#

Python#

from collections import deque
 
class Solution:
    def orangesRotting(self, grid: list[list[int]]) -> int:
        R, C = len(grid), len(grid[0])
        queue = deque()
        fresh = 0
 
        # 1) seed the queue with every rotten cell, count fresh oranges
        for r in range(R):
            for c in range(C):
                if grid[r][c] == 2:
                    queue.append((r, c))
                elif grid[r][c] == 1:
                    fresh += 1
 
        # 2) corner case: nothing to rot
        if fresh == 0:
            return 0
 
        minutes = 0
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
 
        # 3) level-order BFS: drain one minute per loop iteration
        while queue and fresh > 0:
            for _ in range(len(queue)):           # process current level
                r, c = queue.popleft()
                for dr, dc in directions:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] == 1:
                        grid[nr][nc] = 2          # rot it now
                        fresh -= 1
                        queue.append((nr, nc))
            minutes += 1                          # one minute elapsed
 
        return minutes if fresh == 0 else -1

JavaScript#

/**
 * @param {number[][]} grid
 * @return {number}
 */
var orangesRotting = function(grid) {
    const R = grid.length, C = grid[0].length;
    const queue = [];
    let fresh = 0;
 
    // 1) seed queue with all rotten oranges; count fresh
    for (let r = 0; r < R; r++) {
        for (let c = 0; c < C; 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 = [[1, 0], [-1, 0], [0, 1], [0, -1]];
 
    // 2) BFS one level at a time
    while (queue.length && fresh > 0) {
        const size = queue.length;
        for (let i = 0; i < size; i++) {
            const [r, c] = queue.shift();         // dequeue
            for (const [dr, dc] of dirs) {
                const nr = r + dr, nc = c + dc;
                if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
                if (grid[nr][nc] !== 1) continue; // empty or already rotten
                grid[nr][nc] = 2;                 // rot the neighbor
                fresh--;
                queue.push([nr, nc]);
            }
        }
        minutes++;
    }
    return fresh === 0 ? minutes : -1;
};

Time Complexity: O(m times n) — each cell enqueued once. Space Complexity: O(m times n) for the queue worst case.

Common Mistakes#

1. Forgetting the early-return when fresh is 0. If no fresh oranges exist initially, the answer is 0, not the minutes counter (which would still be 0, but only by coincidence — be explicit).
2. Incrementing minutes inside the inner loop. Minutes should only advance once per BFS level. Using a single counter inside the dequeue loop over-counts.
3. Mixing fresh count with grid mutation. If you decrement fresh but forget to set the cell to 2, neighbors keep re-enqueuing it.
4. Returning minutes instead of -1 when fresh remains. The unreachable case is a graded test in this problem.
5. Single-source BFS from each rotten orange. This works but is O((m times n)^2). Multi-source BFS is the canonical fix.

Interview Tips#

• State the multi-source insight upfront. "Because rot spreads from every rotten orange in parallel, this is multi-source BFS — I will seed the queue with every initial source."
• Clarify the return value when no fresh oranges exist. Some interviewers expect 0; some expect -1. Ask before coding.
• Mention the in-place trick. Marking cells as 2 doubles as a visited set; no extra matrix needed.
• Discuss DFS as a wrong choice. DFS does not give shortest distances by default; it would require explicit relaxation. BFS is the natural fit.

Follow-up Questions#

1. What if oranges have variable rot speeds? Use Dijkstra instead of BFS — same multi-source seeding, but with a priority queue.
2. What if rot can move diagonally too? Add four diagonal direction tuples; everything else is identical.
3. How would you parallelize this? Each BFS level is embarrassingly parallel; you can process all cells in a level concurrently.
4. Can you do it without modifying the grid? Yes — use a separate visited set or a distance matrix initialized to infinity.

Key Takeaways#

• Rotting Oranges is the canonical multi-source BFS problem and a Day-1 interview pattern at FAANG companies.
• Seed the queue with every initial source before starting BFS — this is the only difference from single-source BFS.
• Level-order BFS lets you count "minutes elapsed" without per-cell distance storage.
• Always count fresh oranges upfront so you can detect unreachable cells in O(1).
• Marking cells in-place avoids an external visited set and keeps the solution at O(m times n) space.
• This same template solves LC 542, LC 286, LC 1162, and many more — learn it once, reuse it forever.