Rotting Oranges
You are given an m x n grid where each cell is 0 (empty), 1 (a fresh orange), or 2 (a rotten orange). Every minute, any fresh orange adjacent (up, down, left, right) to a rotten orange also becomes rotten. Return the minimum number of minutes until no fresh orange remains, or -1 if that is impossible. Seed the queue with every rotten orange at once — this is multi-source breadth-first search , so all of them spread in lockstep and the elapsed time exactly matches the ring the last fresh orange gets caught in.
Constraints
- 1 ≤ m, n ≤ 10
- gridi[j] is 0, 1, or 2
Example
grid = [[2, 1, 1], [1, 1, 0], [0, 1, 1]]4Explanation The rot spreads outward from (0, 0) in rings; the last fresh orange, at (2, 2), turns rotten in minute 4.
In plain terms
- Multi-source
- Starting the search from several places at the same time, instead of just one, so they all expand outward together.
One cell per orange, in grid order — each shows the minute it turns rotten
Seed the queue with every rotten orange at once — just (0,0) here, so only its slot has a minute. The other six oranges are still fresh.
What happens in this step
queue = [(0,0,min0)] fresh = 6 (the 1s: (0,1),(0,2),(1,0),(1,1),(2,1),(2,2)) Only one source this time. All rotten cells are enqueued together at minute 0 — that's what makes this multi-source BFS.
Steps to visualize
- The row has one slot for each of the seven oranges in the 3x3 grid, read left to right, top to bottom. The two empty cells of the grid are not oranges, so they get no slot.
- A slot shows — while that orange is still fresh, and the minute number once the rot reaches it.
- Seed the queue with every rotten orange at once, at minute 0, and count the fresh oranges.
- Dequeue a rotten orange; for each fresh neighbor, rot it, decrement the fresh count, and enqueue it at minute + 1.
- Track the highest minute reached — that is the elapsed time so far.
- If the fresh count ever hits 0, return the last minute recorded; if the queue empties first, return -1.
Walk through the code
Same walkthrough, now with the code. Press Next to move one step and watch which lines run.
Seed the queue with every rotten orange at once — just (0,0) here, so only its slot has a minute. The other six oranges are still fresh.
What happens in this step
queue = [(0,0,min0)] fresh = 6 (the 1s: (0,1),(0,2),(1,0),(1,1),(2,1),(2,2)) Only one source this time. All rotten cells are enqueued together at minute 0 — that's what makes this multi-source BFS.
Solution
function orangesRotting(grid) {
const rows = grid.length;
const cols = grid[0].length;
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
const 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, 0]);
if (grid[r][c] === 1) fresh++;
}
}
if (fresh === 0) return 0;
let minutes = 0;
while (queue.length > 0) {
const [r, c, time] = queue.shift();
for (const [dr, dc] of dirs) {
const nr = r + dr;
const nc = c + dc;
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === 1) {
grid[nr][nc] = 2;
fresh--;
minutes = time + 1;
queue.push([nr, nc, time + 1]);
}
}
}
return fresh === 0 ? minutes : -1;
}- Time
- O(m * n)
- Space
- O(m * n)
Test cases
| Input | Expected | Covers |
|---|---|---|
grid = [[2, 1, 1], [1, 1, 0], [0, 1, 1]] | 4 | example from the docstring |
grid = [[0, 2]] | 0 | no fresh oranges to begin with |
grid = [[1, 1], [1, 1]] | -1 | fresh oranges but no rotten source at all |
grid = [[2, 1, 0], [0, 0, 0], [0, 1, 1]] | -1 | a row of empty cells seals off a pocket of fresh oranges |
grid = [[2, 1]] | 1 | a single fresh orange one step away |
grid = [[2, 2], [2, 2]] | 0 | every orange already rotten, nothing left to spread |
grid = [[2, 1, 1, 1, 1]] | 4 | the rot has to travel down a straight line of oranges |