Difficulty: MediumGraphs

Rotting Oranges

Problem in Plain English

Each minute, every fresh orange next to a rotten one rots as well. Given the starting grid, return how many minutes pass until no fresh orange remains, or -1 when an isolated fresh orange can never rot.

Problem Statement

You are given an m x n grid where each cell holds 0 for an empty cell, 1 for a fresh orange, or 2 for a rotten orange. Every minute, each fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.

Return the minimum number of minutes that must pass until no cell holds a fresh orange. If some fresh orange can never rot, return -1.

Constraints

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

Examples

Example 1

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

Minute 1 rots (0,1) and (1,0), minute 2 rots (0,2) and (1,1), minute 3 rots (2,1), and minute 4 rots (2,2).

Example 2

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

The fresh orange at (2,0) is cut off by empty cells, so rot never reaches it.

Example 3

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

No fresh orange exists at the start, so zero minutes pass.

Example 4

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

Both endpoint sources spread together. At minute 1 positions 1 and 3 rot; at minute 2 both reach the middle, which is counted only once. Starting from just one source would incorrectly take three minutes to reach all originally fresh cells.

Intuition

Treat nonempty cells as graph vertices connected by shared sides. A fresh orange rots after the shortest number of side-to-side steps from any initially rotten orange, because all sources spread together once per minute. Empty cells block paths. Example 1 needs four steps to reach (2,2), the last fresh cell. Simulating whole minutes works; a queue of only newly rotten cells avoids rescanning inactive cells. A fresh cell with no path from any source makes the answer -1.

Approaches

Minute By Minute Rescan

Solution Details

Reveal Minute By Minute Rescan: intuition, complexity, and code

Intuition

Simulate the clock directly: scan the whole grid every minute and rot fresh neighbours of cells that were already rotten when the minute began. A copied grid keeps newly rotted cells from spreading early, but every minute re-scans cells that have nothing new to report, which is the waste the optimal approach removes.

Step-by-Step Logic

Initialize minutes to 0. For each round, copy every row into next; read neighbours only from the old grid so changes cannot propagate twice in one minute. Example 1 starts with source (0,0).
Scan every rotten cell and set its in-bounds fresh neighbours to rotten in next. Use down, up, right, left direction order. Example 1 changes (1,0) and (0,1) in the first round.
If anything changed, rebind the local grid to next and increment minutes once. This preserves the caller's original rows. In Example 1 minutes becomes 1, then 2 when (0,2) and (1,1) rot.
Repeat whole rounds. Example 1 rots (2,1) at minute 3 and (2,2) at minute 4. Cells that are already rotten remain rotten in every copied state.
Stop on the first unchanged round. Scan the stabilized grid for fresh cells: return -1 if any remain, otherwise minutes. Example 1 performs an unchanged fifth scan and returns 4, not 5.

Why It Works

At the beginning of a round, grid describes exactly the cells rotten after the recorded number of completed minutes. Reading only grid while writing next makes a cell rot in this round exactly when it was fresh and had a rotten neighbour at the start. Induction on rounds therefore reproduces simultaneous spreading, with no same-minute chain reaction. If a round changes nothing, no new source can appear in later rounds, so any remaining fresh orange is unreachable. Otherwise the first round after which all fresh cells disappear is the required elapsed time; the final unchanged scan adds no minute.

Dry Run

Minute By Minute Rescan: variable states at each step
Round / minutes before	Old grid rows	Newly rotten in next	changed	Fresh in next	minutes after / action
1 / 0	211;110;011	(1,0),(0,1)	false → true	6 → 4	adopt 221;210;011; minutes 1
2 / 1	221;210;011	(0,2),(1,1)	false → true	4 → 2	adopt 222;220;011; minutes 2
3 / 2	222;220;011	(2,1)	false → true	2 → 1	adopt 222;220;021; minutes 3
4 / 3	222;220;021	(2,2)	false → true	1 → 0	adopt 222;220;022; minutes 4
5 / 4	222;220;022	none	false	0	discard equal copy; stop
Final scan	222;220;022	no fresh cell	false	0	return 4; caller grid unchanged

Complexity Analysis

Time Complexity

O((m * n)^2)

Space Complexity

O(m * n)

With N = mn cells, at most N changing rounds occur because each changes at least one fresh cell permanently. Each round copies N cells and inspects four neighbours of each rotten cell; the final unchanged round and fresh scan also cost O(N). Total time is O(N²). Several full-grid states can coexist during a round, but only a constant number, so peak auxiliary space is O(N). Total allocation over all rounds can be O(N²), distinct from peak space. Rebinding grid is local in all three languages: the caller's cell values and row identities remain unchanged.

Code

Solution.java

1class Solution {2    public int orangesRotting(int[][] grid) {3        int rows = grid.length;4        int cols = grid[0].length;5        int minutes = 0;6        boolean changed = true;7        while (changed) {8            changed = false;9            // Read the old state for the whole minute; write only to the copy.10            int[][] next = new int[rows][cols];11            for (int r = 0; r < rows; r++) {12                for (int c = 0; c < cols; c++) {13                    next[r][c] = grid[r][c];14                }15            }16            int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};17            for (int r = 0; r < rows; r++) {18                for (int c = 0; c < cols; c++) {19                    if (grid[r][c] == 2) {20                        for (int[] d : dirs) {21                            int nr = r + d[0];22                            int nc = c + d[1];23                            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1) {24                                next[nr][nc] = 2;25                                changed = true;26                            }27                        }28                    }29                }30            }31            if (changed) {32                grid = next;33                minutes++;34            }35        }36        for (int r = 0; r < rows; r++) {37            for (int c = 0; c < cols; c++) {38                if (grid[r][c] == 1) {39                    return -1;40                }41            }42        }43        return minutes;44    }45}

Hints

Hint 1

Rot spreads from every rotten orange at once, so treat all rotten cells as starting points of a single search.

Hint 2

Processing that search level by level makes each level exactly one minute of spreading.

Hint 3

Count the fresh oranges up front, decrement the count as they rot, and return -1 if any remain when the queue empties.

Edge Cases

No fresh orange at the start, as in [[0,2]], so the answer is 0 without any spreading.
Fresh oranges exist but no rotten orange does, so nothing can ever spread and the answer is -1.
A fresh orange walled off by empty cells stays fresh forever, so the answer is -1 even though rot spreads elsewhere.
A single fresh cell [[1]] with no source returns -1; a single rotten or empty cell returns 0. Diagonal proximity to rot does not count as a path.
Multiple sources can meet at the same fresh cell; claim it once. The 10 by 10 maximum may contain a winding path, so elapsed minutes need not equal a simple straight-line distance.
The copied rescan preserves the input and repeats the same answer. BFS mutates reachable fresh oranges; repeating on that object returns 0 if all rotted, or -1 if unreachable fresh cells remain. Copy each row before comparing approaches.

Common Mistakes and Interview Tips

Seeding the queue with a single rotten orange instead of all of them, which staggers the start times and inflates the minute count.
Incrementing the minutes per popped cell instead of per level, which counts cells rather than minutes.
Returning the minute counter without checking the leftover fresh count, which reports a time for grids that never fully rot.
Allowing cells written earlier in a scan to spread immediately causes a same-minute chain reaction. Read an old snapshot or freeze the queue layer.
Using only a shallow outer-array copy shares rows and breaks simultaneous simulation. JavaScript Array.shift can add quadratic queue overhead; use the moving head.
Interview tip: explain the maximum shortest-path distance from all sources and why leftover fresh cells, rather than an empty queue alone, decide impossibility.

Key Takeaway

When many sources spread outward in lockstep, enqueue them all first and read the answer off the breadth-first levels.