Rotting Oranges

You are given a grid where:

• 0 = empty,
• 1 = fresh orange,
• 2 = rotten orange.

Each minute, any fresh orange adjacent (up/down/left/right) to a rotten orange becomes rotten. Return the minimum minutes until no fresh oranges remain, or -1 if impossible.

Why this is worth learning

All initially rotten oranges are simultaneous sources at minute zero. A fresh orange rots at the minimum distance from any source, not after the sum of separate source traversals.

Before coding: one-minute experiment

For row [2,1,1,1,2], when does each fresh orange rot? Why does processing the two sources one after another with separate clocks fail?

Function signature

func OrangesRotting(grid [][]int) int

Inputs / outputs

• grid: rectangular grid.
• Return: minutes to rot all, or -1.

Example

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

Constraints

• 1 <= rows, cols <= 100

Core idea (near-solution)

Running a separate distance search from every rotten cell could compute each fresh cell's nearest source, but repeats traversal. Put all initial sources in one queue at time zero. The first wave claims every cell at nearest-source distance one; the next claims distance two. Mark a fresh cell rotten when enqueued so two sources cannot schedule it twice. The completion time is the largest reached fresh-cell distance, not the sum of source times. Keep a fresh count as a separate reachability check: any remaining fresh orange makes the answer -1.

Invariant: oranges processed at the same BFS depth rot in the same minute.

Algorithm (step-by-step)

1. Enqueue all initially rotten cells and count fresh cells. If there are no fresh cells, return 0.
2. The reference sets minutes = -1 and processes every queued layer, including the initial minute-zero layer.
3. Freeze the layer size. For each cell in that layer, change each fresh orthogonal neighbor to rotten, decrement fresh once, and enqueue the changed cell.
4. Increment minutes after the complete layer. After processing sources it is 0; after processing the last newly rotten layer it equals the last infection time.
5. Once the queue empties, return minutes if fresh is zero, otherwise -1. Do not combine this -1 initialization with an early return immediately when fresh reaches zero; that would need a different clock rule.

Correctness sketch

Before each layer is processed, the queue contains cells first rotten at one common minute. Each fresh neighbor becomes rotten at the next minute and is immediately marked, so it cannot be scheduled again by another source. Induction on distance from the nearest source establishes the earliest rotting time for every reachable orange. The fresh counter decreases once per changed cell. If it reaches zero, the last processed layer gives the required elapsed minutes; if reachable layers end with fresh cells remaining, those cells are separated by empty cells and the answer is -1. No initial fresh cells means zero elapsed time.

Trace (hand walkthrough)

Example input:
grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

Walk:
- minute 0: rotten at (0,0)
- minute 1: rot (0,1),(1,0)
- minute 2: rot (0,2),(1,1)
- minute 3: rot (2,1)
- minute 4: rot (2,2) -> done

Pitfalls to avoid

• Mixing timing conventions. The reference deliberately processes the last layer even when it infects no cells; its -1 initialization accounts for the initial layer.
• Not handling the case of zero fresh oranges at the start.

Debugging lens

Distinguish empty cells from fresh ones, and count actual state changes only once. Test no fresh oranges, fresh cells without a source, and two waves meeting at the same cell.

Complexity

• Time: O(r*c)
• Extra space: O(r*c).

Implementation notes (Go)

• Initialize the queue with all rotten oranges (multi-source BFS).
• Track the count of fresh oranges and minutes by BFS levels.

Contract precision

The reference mutates reachable fresh cells from 1 to 2, including when the final result is -1 because another component is unreachable. Copy the grid for a read-only caller.

Reconstruction checkpoint

For the one-row grid [2,1,1,1,2], assign each initially fresh cell its earliest rot minute and give the completion time. Why does launching independent sequential spreads overcount?

Return to Graph BFS · Module quiz