You are given an m x n grid where each cell holds one of three values:
- 0 — an empty cell,
- 1 — a fresh orange,
- 2 — a rotten orange.
Every minute, any fresh orange that is 4-directionally adjacent (up, down, left, right) to a rotten orange becomes rotten too. All such rottings happen simultaneously each minute.
Return the minimum number of minutes that must elapse until no cell has a fresh orange. If it is impossible for every fresh orange to rot (one is fenced off from all rotten oranges), return -1.
Example
The rot fans out one ring per minute; the last fresh orange (bottom-right) rots at minute 4.
Constraints
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 10
- grid[i][j] is 0, 1, or 2.
Intuition
Each minute, every fresh orange touching rot turns rotten. The literal simulation: sweep the whole grid once per minute, marking which fresh oranges have a rotten neighbour, then flip them all — and repeat until a full sweep changes nothing.
function orangesRotting(grid) {
const rows = grid.length, cols = grid[0].length;
let minutes = 0;
while (true) {
const toRot = [];
// Full sweep: find every fresh orange adjacent to a rotten one.
for (let r = 0; r < rows; r++)
for (let c = 0; c < cols; c++)
if (grid[r][c] === 1)
for (const [nr, nc] of [[r+1,c],[r-1,c],[r,c+1],[r,c-1]])
if (nr>=0&&nc>=0&&nr<rows&&nc<cols && grid[nr][nc] === 2)
{ toRot.push([r, c]); break; }
if (toRot.length === 0) break; // a minute with no change → stop
for (const [r, c] of toRot) grid[r][c] = 2;
minutes++;
}
for (const row of grid) if (row.includes(1)) return -1; // some fresh orange stranded
return minutes;
}Re-scanning the entire grid every single minute is the waste — most cells aren't near the action. Can we do better?
The key observation: the rot spreads outward one ring per minute from all current rotten oranges at once. That is exactly a multi-source [BFS](/study-guide/algos/topic/breadth-first-search) — seed the queue with every rotten orange, then expand level by level, where each BFS level is one minute. A fresh orange's rotting time is simply its grid distance to the nearest rot source, which BFS measures for free. Track the count of fresh oranges; if any remain after the queue drains, they were unreachable, so return -1.
The diagram is a gridWalkthrough over the real board (2=rotten, 1=fresh, 0=empty). Newly-rotted cells are marked each frame; the section grid is overridden per frame to show the spread. Walking it through:
multi-source BFS — the rotten frontier (marked) grows one ring per minute
Only (0,0) is rotten at the start, and there are 6 fresh oranges. BFS begins with the single source.
The first ring: the two fresh neighbours of (0,0) rot. Fresh count drops 6 → 4.
Second ring out from the cells that rotted last minute. Fresh count 4 → 2, leaving (2,1) and (2,2).
(2,1) sits below (1,1) and rots this minute, leaving only (2,2) fresh. The (1,2)=0 empty cell is a gap the rot has to route around.
The last fresh orange (2,2) rots from its neighbour (2,1). No fresh oranges remain, so the answer is the 4 minutes elapsed.
Optimization
Multi-source BFS
Because all the rot spreads one ring per minute, the time a fresh orange takes to rot is its grid distance to the nearest rotten orange — exactly what a breadth-first search measures. Seed the BFS queue with every rotten orange at once (a multi-source BFS), and expand level by level: each level is one minute.
Track the number of fresh oranges up front. Each time the BFS rots a fresh orange, decrement that counter. The answer is the number of full levels processed; if any fresh orange remains when the queue drains, it was unreachable, so return -1.
O(m·n) time — every cell enters the queue at most once — and O(m·n) space for the queue.
function orangesRotting(grid) {
const rows = grid.length;
const cols = grid[0].length;
// Seed the frontier with every rotten orange, and count the fresh ones.
let queue = [];
let fresh = 0;
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (grid[r][c] === 2) queue.push([r, c]);
else if (grid[r][c] === 1) fresh++;
}
}
let minutes = 0;
// Expand one ring (one minute) per outer iteration, until nothing fresh borders the rot.
while (queue.length > 0 && fresh > 0) {
const next = [];
for (const [r, c] of queue) {
for (const [nr, nc] of [[r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]]) {
if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
if (grid[nr][nc] !== 1) continue; // only fresh oranges rot
grid[nr][nc] = 2; // rot it now so it isn't queued twice
fresh--;
next.push([nr, nc]);
}
}
queue = next;
minutes++; // a full ring spread = one minute
}
// Any fresh orange left was unreachable from all rot sources.
return fresh === 0 ? minutes : -1;
}Complexity analysis
Time complexity: O(m·n). Here's why:
- The initial sweep that seeds the queue and counts fresh oranges is one pass over
m·ncells. - During the BFS, each cell is enqueued at most once and its four neighbours inspected a constant number of times.
Both phases are linear in the grid size, so the total is O(m·n).
Space complexity: O(m·n). Here's why:
- The BFS frontier holds at most
O(m·n)cells (a grid that is entirely rotten at the start seeds every cell). - The grid is rotted in place, so no copy is made.
The dominant extra space is the O(m·n) queue.
Test cases
Beyond the example above, these are worth thinking through before you submit.
| Input | Expected output | Description |
|---|---|---|
| grid = 0 | 0 | An empty cell — nothing fresh, zero minutes. |
| grid = 222 | 0 | All already rotten — zero minutes elapse. |
| grid = 111 | -1 | All fresh, no source — they never rot, return -1. |
| grid = 211 111 111 | 4 | A solid block of fresh oranges with one rotten corner — the far corner rots at minute 4. |
| grid = 21001 00000 | -1 | (0,1) rots from the source, but (0,4) is fenced off by empties and never rots — impossible. |
Try it yourself
Write your solution against the real judge before checking the reference.