Free lesson · DSA Mastery - Interview Prep, End to End

Rotting Oranges

Hard9 min readdsagraphs

Rotting Oranges

Rotting Oranges opens the BFS Problems sub-group and is the canonical multi-source BFS problem: in a grid of fresh oranges, rotten oranges, and empty cells, rot spreads each minute from every rotten orange to adjacent fresh ones; return the minutes until no fresh orange remains, or -1 if some can never rot. The technique is exactly the multi-source BFS established in the introduction - seed the queue with all initially-rotten oranges at time 0, then BFS level by level, where each level is one minute, until the queue empties; the answer is the last level reached. It launches the BFS sub-group's central theme: unweighted shortest "time" or "distance" via level-counted breadth-first traversal. We present the multi-source level-BFS (canonical).

The insight: rot spreads from all rotten oranges simultaneously, one ring per minute - exactly the multi-source wavefront. Seed the queue with every initially-rotten orange at time 0, count the fresh oranges, then BFS level by level: each level rots all fresh oranges adjacent to the current rotten frontier, taking one minute. The number of levels until the frontier can't expand is the time for the last orange to rot. If any fresh orange is never reached (the fresh count doesn't hit zero), it's unreachable - return -1.

The Problem

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, or
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.

Example 1:

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

Explanation: Rot spreads from (0,0). After 4 minutes, every fresh orange has rotted.

Example 2:

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

Explanation: The orange at (2,0) is never reached (blocked by empty cells) - impossible.

Constraints:

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

Approaches Overview

#	Approach	Time	Space	Verdict
1	Multi-source BFS, level = minute	O(m × n)	O(m × n)	Canonical

This is multi-source BFS with level-counting. Seed the queue with all initially-rotten oranges (time 0) and count fresh oranges. BFS level by level: each level processes the current rotten frontier, rotting adjacent fresh oranges (decrementing the fresh count) and enqueuing them as the next frontier; increment the minute counter per level that produces new rot. When the queue empties, return the elapsed minutes if no fresh orange remains, else -1. O(m × n) - each cell enqueued once.

Approach: Multi-Source Level-BFS - Canonical

The Idea

Scan the grid: enqueue every rotten orange (value 2) and count fresh oranges (value 1). If there are no fresh oranges, return 0 immediately. Then BFS level by level: for each minute, process exactly the oranges currently in the queue (the current rot frontier); for each, rot any fresh 4-neighbor (set to 2, decrement fresh count, enqueue). Increment minutes after a level that rotted at least one orange. When the queue empties, return minutes if fresh == 0, else -1.

Logic Flowchart

graph TD
    A["scan: enqueue all rotten (2); count fresh (1)"] --> B{"fresh == 0?"}
    B -->|Yes| C["return 0"]
    B -->|No| D["minutes = 0"]
    D --> E{"queue non-empty AND fresh > 0?"}
    E -->|No| F{"fresh == 0?"}
    E -->|Yes| G["process one level: rot fresh neighbors, decrement fresh, enqueue"]
    G --> H["minutes++"]
    H --> E
    F -->|Yes| I["return minutes"]
    F -->|No| J["return -1 (some fresh unreachable)"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style C fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style D fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style E fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style F fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style G fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style H fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style I fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style J fill:#dc2626,stroke:#ef4444,color:#f1f5f9

This flowchart shows Rotting Oranges. All rotten oranges seed the queue at time zero; each BFS level is one minute that rots adjacent fresh oranges, and the answer is the minutes elapsed or minus one if fresh oranges remain.

Code

private static final int[] DR = {-1, 1, 0, 0};
private static final int[] DC = {0, 0, -1, 1};

public static int orangesRotting(int[][] grid) {
    int m = grid.length, n = grid[0].length, fresh = 0;
    Queue<int[]> queue = new ArrayDeque<>();
    for (int r = 0; r < m; r++)
        for (int c = 0; c < n; c++) {
            if (grid[r][c] == 2) queue.offer(new int[]{r, c});   // seed all rotten
            else if (grid[r][c] == 1) fresh++;                   // count fresh
        }
    if (fresh == 0) return 0;                                    // nothing to rot

    int minutes = 0;
    while (!queue.isEmpty() && fresh > 0) {
        int size = queue.size();                                 // current rot frontier
        for (int i = 0; i < size; i++) {
            int[] cell = queue.poll();
            for (int d = 0; d < 4; d++) {
                int nr = cell[0] + DR[d], nc = cell[1] + DC[d];
                if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 1) {
                    grid[nr][nc] = 2;                            // rot it
                    fresh--;
                    queue.offer(new int[]{nr, nc});              // next frontier
                }
            }
        }
        minutes++;                                               // one minute per level
    }
    return fresh == 0 ? minutes : -1;                            // leftover fresh → impossible
}

// Usage:
// orangesRotting([[2,1,1],[1,1,0],[0,1,1]]) -> 4
// orangesRotting([[2,1,1],[0,1,1],[1,0,1]]) -> -1

This Java code rots oranges with multi-source BFS: it seeds all rotten oranges, then each level rots adjacent fresh oranges and counts a minute, returning the minutes elapsed or minus one if fresh oranges remain.

Step-by-Step Walkthrough

A frame-by-frame trace on Example 1, [[2,1,1],[1,1,0],[0,1,1]]:

graph LR
    F0["seed (0,0)=rotten. fresh=6. minutes=0"]
    F1["min1: rot (0,1),(1,0). fresh=4. min2: rot (0,2),(1,1). fresh=2"]
    F2["min3: rot (2,1). fresh=1. min4: rot (2,2). fresh=0"]
    F3["queue empties, fresh==0 → return minutes=4"]
    F0 --> F1 --> F2 --> F3

    style F0 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F1 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F2 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F3 fill:#16a34a,stroke:#10b981,color:#f1f5f9

This walkthrough rots oranges: starting from the one rotten orange, each minute the rot spreads to adjacent fresh oranges, taking four minutes to rot all six fresh oranges.

Result: 4.

Complexity

Time: O(m × n) - each cell enqueued and processed once. Space: O(m × n) for the queue.

Complexity Comparison

Approach	Time	Space	Key Idea
Multi-source level-BFS	O(m × n)	O(m × n)	Seed all rotten at time 0; level = minute

Multi-source level-BFS is the standard solution: the rot spreads from all rotten oranges in parallel, exactly a multi-source wavefront, so seeding the queue with every rotten orange and counting levels gives the minutes for the last orange to rot. The fresh count detects impossibility - if it never reaches zero, some orange was unreachable. This is the canonical "minimum time for a multi-origin spread" problem, launching the BFS sub-group.

Variations & Follow-ups

Why is this multi-source BFS rather than running BFS from each rotten orange?

The rot spreads from every rotten orange simultaneously - at minute 1, all oranges adjacent to any rotten orange become rotten, not just those near one particular rotten orange. This is precisely the multi-source wavefront: many origins expanding in lockstep, one ring per minute. Running a separate BFS from each rotten orange and combining would be wasteful and awkward (you'd have to take the minimum arrival time per cell across all sources). Instead, seeding the queue with all rotten oranges at time 0 makes them expand together: the first BFS level rots everything adjacent to the combined frontier, the second level the next ring, and so on. Because BFS reaches each fresh orange by the fewest steps, the level at which an orange rots is the minute it actually rots (the nearest rotten orange reaches it first). This is the multi-source BFS technique from the introduction - seed the frontier with everything at distance 0 - applied to a spreading process where the level number is elapsed time. Recognizing "spreads from many origins at once" as the signal for multi-source seeding is the key reframing.

Why does the level count equal the elapsed minutes, and how does the level-by-level processing work?

Each BFS level corresponds to exactly one minute of spreading: level 0 is the initial rotten oranges (minute 0), level 1 is everything that rots in minute 1, level 2 in minute 2, and so on. So counting levels counts minutes. To process level by level, capture int size = queue.size() at the start of each iteration - this is the number of oranges in the current rot frontier (those that rotted in the previous minute). Then dequeue exactly size oranges, rotting their fresh neighbors and enqueuing those (which form the next minute's frontier) without processing them in this round. After the inner loop, increment minutes. This separation keeps each minute's spread distinct: the oranges enqueued during minute t's processing belong to minute t+1 and aren't processed until the next outer iteration. Without capturing size upfront, the newly-rotted oranges would blur into the current level, collapsing all minutes into one and giving the wrong count. The level-by-level technique (from the BFS introduction topic) is essential whenever the level number carries meaning - here, time.

Why count fresh oranges, and how does it detect the impossible case?

The fresh-orange counter serves two purposes: it tells you when to stop (all fresh oranges rotted → fresh == 0) and it detects impossibility. Some fresh oranges may be unreachable - completely surrounded by empty cells (value 0), with no path for rot to reach them, as in Example 2's isolated orange at (2,0). The BFS wavefront can only spread through adjacent oranges; it can't cross empty cells. So when the queue empties (the rot can't spread any further), if fresh > 0, those remaining fresh oranges were never reached and never will rot - the answer is -1 (impossible). If fresh == 0, every orange rotted and the elapsed minutes is the answer. Tracking the fresh count is cleaner than re-scanning the grid at the end to check for leftover fresh oranges (though that works too). It also enables the early exit: stop the BFS as soon as fresh == 0 (no need to drain the queue further). The counter is the natural "are we done, and was it possible?" signal - a small but important piece of bookkeeping that distinguishes Rotting Oranges from a plain reachability BFS.

Why initialize minutes carefully, and what are the subtle counting traps?

The minute counting has two classic traps. First, the all-fresh-already-rotten or no-fresh case: if there are zero fresh oranges at the start, the answer is 0 (no time needed) - handle this before the BFS loop, or you might return a spurious count. Second, over-counting by one: if you increment minutes unconditionally on every loop iteration including the final one where nothing new rots, you can overshoot. The guard while (!queue.isEmpty() && fresh > 0) helps - it stops as soon as all fresh oranges are gone, so you don't run an extra empty level. The structure here increments minutes once per level that processes the frontier, and the fresh > 0 condition ensures you don't count a final level after everything's rotted. Carefully: the last productive level rots the final fresh orange and increments to the correct minute, then the loop exits because fresh == 0. Getting these boundaries right - initialize for the no-fresh case, stop when fresh hits zero, don't add a phantom final minute - is where Rotting Oranges trips people up. It's worth tracing a tiny example (one rotten, one adjacent fresh: answer 1) to confirm the counting.

What about edge cases?

No fresh oranges initially: Return 0 (nothing to rot).
No rotten oranges but fresh exist: Queue starts empty; the loop doesn't run; fresh > 0 → return -1.
Unreachable fresh orange (Example 2): The wavefront can't reach it; fresh stays positive → -1.
All cells empty: No fresh, no rotten → 0.
Single rotten orange spreading to all: The level count is the distance to the farthest fresh orange.

Common Interview Pitfalls

Running BFS per rotten orange. Seed all rotten oranges into one queue (multi-source); per-source is redundant.
Not capturing queue.size() per level. Newly-rotted oranges blur into the current minute, breaking the time count.
Forgetting the no-fresh-at-start case. Return 0 immediately if there are no fresh oranges.
Not detecting unreachable oranges. Check fresh == 0 at the end; leftover fresh means -1.

Why This Topic Matters

Rotting Oranges is the canonical multi-source BFS problem and the BFS sub-group's opener: seed the queue with all rotten oranges at time 0, then BFS level by level where each level is one minute, and the answer is the elapsed minutes (or -1 if a fresh orange is unreachable, detected via the fresh count). It cements that a multi-origin spreading process maps to multi-source BFS with the level number as elapsed time - the central theme of the entire sub-group.

The next topic, 01 Matrix, applies the same multi-source BFS to a distance question: given a binary matrix, find for each cell its distance to the nearest 0. The trick is to seed the BFS queue with all the zero cells at distance 0 (rather than BFS outward from each 1), then expand the combined frontier so each 1 cell receives the distance at which the wavefront first reaches it - its distance to the nearest zero. It is the distance-flavored twin of Rotting Oranges, reinforcing that "distance to the nearest of many targets" is one multi-source BFS, not many single-source ones.

Back to DSA Mastery - Interview Prep, End to End