Rotting Oranges

1. Problem & Core Objective

A grid contains 0 (empty), 1 (fresh orange), 2 (rotten orange). Each minute, a rotten orange rots all four-directionally adjacent fresh oranges. Return the minutes until no fresh orange remains, or -1 if that's impossible.

2 1 1
1 1 0     →  4
0 1 1

2 1 1
0 1 1     →  -1      (the bottom-left orange can never be reached)
1 0 1

Constraints: 1 <= m, n <= 10 · cells are 0, 1, or 2

What's actually being tested: the same multi-source BFS as question 4, plus two additions — counting levels rather than per-cell distances, and detecting the unreachable case. The -1 is where most solutions go wrong.

2. First-Principles Thought Process

It's question 4 with a different story

Rotten oranges are the sources. Fresh oranges are the cells to reach. "Minutes elapsed" is BFS depth.

All initially-rotten oranges rot their neighbours simultaneously, which is exactly multi-source BFS: seed them all at level 0.

Levels, not distances

Question 4 wrote a distance into each cell. Here the answer is the number of rounds — the depth of the last level processed.

That needs the level-snapshot idiom from level-order traversal:

int size = q.size();                  // freeze this minute's rotten oranges
for (int i = 0; i < size; i++) { ... }   // anything added belongs to the NEXT minute
minutes++;

Without the snapshot, the loop drains the whole queue and reports 1 minute for everything.

Detecting the impossible case

If some fresh orange is unreachable — walled off by empty cells — the answer is -1.

The clean way is to count fresh oranges up front and decrement as each one rots. At the end, a non-zero count means some were never reached.

That's much more reliable than scanning the grid afterwards, and it costs nothing since the initial scan already runs to find the sources.

The off-by-one that bites

minutes increments once per level, including the last level — which only discovers that nothing new rotted.

Two standard fixes: only increment when the level actually rotted something, or increment unconditionally and subtract 1 at the end. The first is clearer about intent.

And if there were no fresh oranges to begin with, the answer is 0, not -1 — nothing needs to rot.

3. Solution Paths

Approach 1 — Simulate minute by minute over the whole grid (brute force)

public int orangesRotting(int[][] grid) {
    int minutes = 0;
    while (true) {
        List<int[]> toRot = new ArrayList<>();
        for (int r = 0; r < grid.length; r++)                // rescan the entire grid
            for (int c = 0; c < grid[0].length; c++)
                if (grid[r][c] == 1 && hasRottenNeighbour(grid, r, c))
                    toRot.add(new int[]{r, c});

        if (toRot.isEmpty()) break;
        for (int[] cell : toRot) grid[cell[0]][cell[1]] = 2;
        minutes++;
    }
    return anyFreshLeft(grid) ? -1 : minutes;
}

• Time O(m · n · minutes) = O((m·n)²) worst case · Space O(m·n)

Counter-questions on this approach

⭐ "What's the repeated work?"

Every minute rescans all m · n cells to find which fresh oranges are adjacent to rotten ones — even though only the oranges that rotted last minute can cause new rotting.

BFS already tracks exactly that set in its queue. The frontier is the answer to "what changed"; rescanning rediscovers it.

⭐ "Why does it collect into toRot instead of rotting in place?"

Because rotting during the scan would let a newly-rotten orange rot its neighbour in the same minute, cascading across the grid instantly. The whole grid must update simultaneously.

That's the same discipline as the level snapshot in BFS — freeze this round's state before producing the next. Rotting in place is the classic bug here and it makes everything rot in one or two minutes.

"Is O((m·n)²) a problem at 10 × 10?"

No — 100 cells and at most 100 minutes is 10,000 operations. It would pass easily.

The objection is that it rediscovers the frontier every round when BFS maintains it for free, and the BFS version is shorter.

Approach 2 — Multi-source BFS counting levels (optimal)

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

public int orangesRotting(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    Queue<int[]> q = new ArrayDeque<>();
    int fresh = 0;

    for (int r = 0; r < m; r++)                        // one scan: seed AND count
        for (int c = 0; c < n; c++) {
            if (grid[r][c] == 2) q.offer(new int[]{r, c});
            else if (grid[r][c] == 1) fresh++;
        }

    if (fresh == 0) return 0;                          // nothing to rot

    int minutes = 0;
    while (!q.isEmpty() && fresh > 0) {
        int size = q.size();                           // freeze THIS minute's rotten set
        for (int i = 0; i < size; i++) {
            int[] cell = q.poll();
            for (int[] d : DIRS) {
                int nr = cell[0] + d[0], nc = cell[1] + d[1];
                if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
                if (grid[nr][nc] != 1) continue;       // empty or already rotten

                grid[nr][nc] = 2;                       // rot on discovery
                fresh--;
                q.offer(new int[]{nr, nc});
            }
        }
        minutes++;                                      // one full minute elapsed
    }

    return fresh == 0 ? minutes : -1;                   // leftovers = unreachable
}

Trace — example 1:

Answer 4 ✓

• Time O(m · n) · Space O(m · n)

Counter-questions on this approach

⭐ "Why count fresh up front instead of scanning the grid at the end?"

Because the count is maintained for free — I'm already scanning to seed the queue, and each rotting decrements it. A final scan is another O(m·n) pass and, more importantly, it's easy to get wrong if the grid was mutated unexpectedly.

The counter also gives a clean loop guard: fresh > 0 stops the moment everything has rotted, avoiding a wasted final level.

⭐ "Why is the int size = q.size() snapshot necessary?"

Because oranges rot simultaneously each minute. Inside the loop I enqueue newly-rotten oranges, and those belong to the next minute. Without freezing the size, the inner loop would drain the whole queue and the whole grid would rot in one round.

It's exactly the level-order idiom from tree BFS, and it's what makes minutes meaningful.

⭐ "Explain the off-by-one on minutes."

minutes++ runs after each level. The danger is incrementing for a level that rotted nothing — the last round would then over-count by one.

I avoid it with the fresh > 0 loop condition: once the final orange rots, fresh hits 0 and the loop exits immediately without another increment. So the count is exactly the number of productive rounds.

The alternative — incrementing unconditionally and returning minutes - 1 — also works but reads worse, and it breaks if the queue was empty to start.

⭐ "Why return 0 when there are no fresh oranges?"

Because nothing needs to rot, so zero minutes elapse — not -1. A grid of all empty cells, or all rotten, should return 0.

This is the case most solutions get wrong. Without the early return, the loop wouldn't run, minutes would stay 0, and fresh == 0 would still return 0 — so it happens to work here. But making it explicit documents the intent and protects against a restructured loop.

"Why rot on discovery rather than when dequeued?"

Same as question 4: it's the visited marker, and it prevents the same orange being enqueued from two rotten neighbours in the same minute. Without it, fresh would be decremented twice and the count would go negative.

"What if the grid is all 0s?"

fresh == 0 returns 0 immediately. Correct — no oranges, nothing to wait for.

Comparison

4. Why the Optimal Wins

The simulation rescans the entire grid each minute to find which oranges are adjacent to newly-rotten ones. BFS's queue is that set — maintaining it costs nothing, because it's produced as a side effect of the previous round.

It also handles the simultaneity requirement for free: the level snapshot separates this minute's rotten oranges from next minute's, where the simulation needs an explicit collect-then-apply phase to avoid cascading.

The framing worth keeping:

Multi-source BFS again — but here the answer is the number of LEVELS, not a per-cell distance. Snapshot q.size() to separate the minutes, and track a fresh count so leftovers mean -1.

5. Java Prerequisites

Seed and count in one pass

if (grid[r][c] == 2) q.offer(new int[]{r, c});
else if (grid[r][c] == 1) fresh++;

Level-by-level BFS

while (!q.isEmpty() && fresh > 0) {
    int size = q.size();                   // freeze the current level
    for (int i = 0; i < size; i++) { ... } // enqueued items belong to the next level
    minutes++;
}

Rot on discovery — the assignment is both the state change and the visited marker.

The -1 decision — return fresh == 0 ? minutes : -1;. A remaining fresh orange is unreachable.

6. Interview Communication Guide

Clarifying questions: Do all rotten oranges spread simultaneously (yes)? Are diagonals included (no)? What if there are no fresh oranges (return 0, not -1 — the key edge case)? What if there are no rotten ones but some fresh (-1)? May I modify the grid (yes)?

The pitch

"This is the same multi-source BFS as Walls and Gates, with a different story. Rotten oranges are the sources, fresh ones are the cells to reach, and minutes are BFS levels.

All initially-rotten oranges spread simultaneously, so I seed the queue with all of them before starting — they're all at level 0 together.

Two differences from the previous question. First, the answer is the number of levels, not a per-cell distance, so I need the level snapshot: freeze q.size() at the top of each round, process exactly that many, and anything enqueued during the round belongs to the next minute. Without that, the whole grid rots in one round.

Second, I have to detect the impossible case. I count the fresh oranges during the seeding scan — which I'm doing anyway — and decrement each time one rots. If any remain at the end, they were unreachable, so return -1.

That counter also gives a clean loop guard. Stopping on fresh > 0 means the loop exits the instant the last orange rots, so minutes never counts a final unproductive round. That's the off-by-one this problem is known for.

And the case most solutions miss: no fresh oranges at all returns 0, not -1. Nothing needs to rot.

O(m·n) — each cell is enqueued at most once.

The naive simulation rescans the whole grid every minute to find which oranges are next to rotten ones. BFS's queue already is that set."

Edge cases to volunteer:

Name the all-empty grid and the single fresh orange. The first must return 0 and is the classic miss; the second must return -1 and checks that an absent source is handled rather than assumed.

7. Follow-Up Questions — Modified Constraints

⭐ "Return which orange rots last."

Track the cell dequeued in the final productive level. One extra variable, same sweep. Useful because it's the cell farthest from every source — the grid's "eccentricity" with respect to the rotten set.

⭐ "Oranges rot at different rates depending on the cell."

BFS breaks — the wavefront is only time-ordered under uniform cost. You'd need Dijkstra with a priority queue, seeded with all rotten oranges at time 0. O(m·n log(m·n)).

"Diagonal spreading as well."

Extend DIRS to eight offsets. Nothing else changes, and more cells become reachable so fewer -1 cases occur.

"What if oranges could be added over time?"

That's a dynamic problem. Each new rotten orange can be BFS'd outward, stopping wherever existing rot times are already earlier. A new fresh orange needs checking against its neighbours' rot times. Removing a rotten orange is much harder — you'd have to recompute everything that depended on it.

"What if the grid were 1000 × 1000?"

Still O(m·n) = 10^6, fine. But a million int[] objects in the queue is wasteful — encode coordinates as r * n + c in an ArrayDeque<Integer>, or use an int[] ring buffer.

"Return the full rot-time grid instead of the total."

That's Walls and Gates exactly — write time into each cell as it rots rather than counting levels. Two problems, one algorithm, and the difference is only what you record.