Rotting Oranges: Multi-Source BFS, Where Every Layer Is a Minute
The multi-source BFS solution to Rotting Oranges, explained step by step — intuition, JavaScript code, a worked walkthrough, complexity, and common mistakes.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Rotting Oranges looks like a simulation puzzle, but it is really a question about time: how many rounds does it take for something to spread everywhere? The answer to that question is always the same structure — breadth-first search, where each BFS layer is one tick of the clock.
The twist that makes it the canonical teaching example: rot doesn't spread from one source. Every rotten orange spreads simultaneously, so the search starts from all of them at once — multi-source BFS, the same shape behind walls-and-gates, nearest-exit, and 01-matrix problems.
The queue is the whole trick. A stack (DFS) follows one trail of rot as deep as it can go — that's a spread order, not the fastest one. A queue processes cells in the exact order rot reaches them, which is precisely what "minimum minutes" means.
The problem
You're 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 4-directionally adjacent to a rotten one becomes rotten. Return the minimum number of minutes until no fresh orange remains — or -1 if that's impossible.
Input: grid = [[2,1,1],
[1,1,0],
[0,1,1]]
Output: 4 // rot reaches the far corner (2,2) after 4 minutesTwo constraints in that statement drive the design:
- Spread is simultaneous — every rotten orange infects its neighbors in the same minute, so you can't process one source to completion before starting the next.
- You must detect unreachable fresh oranges — a fresh orange walled off by
0s never rots, and the answer becomes-1, not "however long the rest took".
The brute force baseline
The literal approach simulates the rules: scan the whole grid, find every fresh orange touching a rotten one, rot them all at once, repeat until a full pass changes nothing.
function orangesRotting(grid) {
const rows = grid.length, cols = grid[0].length;
let minutes = 0;
while (true) {
const toRot = [];
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (grid[r][c] !== 1) continue;
const nearRotten =
(r > 0 && grid[r - 1][c] === 2) ||
(r < rows - 1 && grid[r + 1][c] === 2) ||
(c > 0 && grid[r][c - 1] === 2) ||
(c < cols - 1 && grid[r][c + 1] === 2);
if (nearRotten) toRot.push([r, c]);
}
}
if (toRot.length === 0) break; // nothing changed → done
for (const [r, c] of toRot) grid[r][c] = 2;
minutes++;
}
return grid.some((row) => row.includes(1)) ? -1 : minutes;
}This is correct — collecting toRot before flipping cells keeps newly rotted oranges from infecting neighbors within the same minute. But it's wasteful: every minute re-scans all m*n cells even though almost none are on the rot frontier. In a snake-shaped corridor, rot advances one cell per minute, so there can be up to m*n minutes — O((m·n)²) total. All that rescanning exists only because we've lost track of where the rot currently is.
The key insight: BFS layers are minutes
Keep track of the frontier explicitly. Put every rotten orange into a queue, then expand outward one ring at a time. Because a queue is first-in, first-out, everything rotted at minute 1 is processed before anything rotted at minute 2 — the queue is the frontier, in chronological order.
The multi-source part is the elegant bit: seed the queue with all rotten oranges before the loop starts. Like dropping several stones into a pond at once, the ripples expand together, and each cell is first touched by whichever source is nearest — that first-touch time is exactly the minute the orange rots, with zero extra bookkeeping.
Two counters complete the algorithm:
fresh— count fresh oranges up front. When it hits 0, everything has rotted; if the queue drains while it's still positive, some orange was unreachable →-1.minutes— increment once per layer, not per cell. Snapshot the queue length before the inner loop so oranges rotted this minute don't spread until the next one.
The optimal solution
This is the exact algorithm the visualizer steps through:
function orangesRotting(grid) {
const rows = grid.length;
const cols = grid[0].length;
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]);
if (grid[r][c] === 1) fresh++;
}
}
let minutes = 0;
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
while (queue.length > 0 && fresh > 0) {
const size = queue.length;
for (let i = 0; i < size; i++) {
const [r, c] = queue.shift();
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === 1) {
grid[nr][nc] = 2;
fresh--;
queue.push([nr, nc]);
}
}
}
minutes++;
}
return fresh === 0 ? minutes : -1;
}The fresh > 0 in the loop condition quietly fixes two classic bugs at once. If the grid starts with no fresh oranges, the loop never runs and you correctly return 0. And the loop exits the instant the last orange rots — so you never pay the off-by-one of processing a final layer that rots nothing while still incrementing minutes.
Marking neighbors rotten (grid[nr][nc] = 2) at enqueue time doubles as the visited set — no cell can enter the queue twice, because by the time anyone else looks at it, it's no longer a 1.
Walkthrough: grid = [[2,1,1],[1,1,0],[0,1,1]]
Setup pass: queue = [(0,0)], fresh = 6, minutes = 0. Each table row is one full while-loop iteration — one minute.
| Minute | Queue at start of layer | Rotted this minute | fresh after | minutes after |
|---|---|---|---|---|
| 1 | [(0,0)] | (1,0), (0,1) | 4 | 1 |
| 2 | [(1,0), (0,1)] | (1,1), (0,2) | 2 | 2 |
| 3 | [(1,1), (0,2)] | (2,1) | 1 | 3 |
| 4 | [(2,1)] | (2,2) | 0 | 4 |
Minute 3 shows the visited-marking payoff: most neighbors of (1,1) and (0,2) are already 2 and get skipped instantly — only the genuinely fresh (2,1) is enqueued. After minute 4, fresh === 0, the loop condition fails, and the function returns 4. Wall off a fresh orange with 0s and the queue instead drains with fresh still positive — the -1 path. Watch both endings play out in the interactive visualizer, which animates the queue and the fresh counter at every step.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Repeated full-grid scans | O((m·n)²) | O(m·n) | up to m·n minutes, each rescanning every cell |
| DFS with per-cell min timestamps | O((m·n)²) worst case | O(m·n) | cells get revisited whenever a shorter rot time is found |
| Multi-source BFS | O(m·n) | O(m·n) | every cell enqueued at most once, 4 neighbor checks each |
BFS wins because each cell does constant work exactly once. The space is the queue plus nothing — the grid itself stores visited state. One practical note: queue.shift() is O(n) in JavaScript arrays, which technically makes this implementation O((m·n)²) in the worst case — irrelevant at LeetCode's 10×10 constraint, and fixable with a read-index pointer if the grid were large.
Common mistakes
- Running DFS. A fresh orange near two rotten sources rots at the time of the nearer one; DFS from the farther source records the wrong minute unless you add messy min-timestamp corrections.
- Not snapshotting the layer size. If the inner loop reads
queue.lengthlive instead of cachingconst size = queue.length, oranges rotted this minute spread again within the same minute, and the answer comes out too small. - The off-by-one on minutes. Looping on
queue.length > 0alone processes one final layer that rots nothing, leavingminutesone too high. Thefresh > 0guard is the clean fix;Math.max(0, minutes - 1)is the patch. - Forgetting the
-1and0edge cases. All-rotten or all-empty grids must return0; a fresh orange sealed off by0s must yield-1. The up-frontfreshcounter handles both. - Marking rotten at dequeue instead of enqueue. Flip the cell only when it leaves the queue and two sources can enqueue the same fresh orange in one layer —
freshgets decremented twice and the answer corrupts.
Where this pattern shows up next
Rotting Oranges is the queue showcase of this section — FIFO order is what makes "layer = minute" true. Its siblings train the opposite discipline, LIFO, where the most recent thing matters instead of the oldest:
- Valid Parentheses — the purest stack problem: the most recent opener must close first.
- Min Stack — augmenting a stack so history-dependent state (the running minimum) pops back into place for free.
- Remove Outermost Parentheses — replacing an explicit stack with a depth counter.
- Evaluate Reverse Polish Notation — a stack as the execution engine for postfix expressions.
Seeing queue-BFS and stack problems side by side is the fastest way to internalize when order-of-arrival matters (queue) versus order-of-nesting (stack).
FAQ
Why does Rotting Oranges use BFS instead of DFS?
Because the problem asks for the minimum time, and rot spreads from all sources simultaneously. BFS processes cells in increasing distance from the nearest rotten source, so the layer number at which a cell is reached is the minute it rots. DFS commits to one path at a time; a cell reachable in 2 minutes from one source might be visited via a 7-step path from another, recording the wrong time unless you add per-cell minimum-timestamp corrections and revisits.
What is multi-source BFS and why seed all rotten oranges at once?
Multi-source BFS is ordinary BFS whose queue starts with several nodes instead of one — as if all sources were connected to an imaginary super-source at distance 0. Seeding every rotten orange before the loop means each fresh orange is reached first by its nearest source, so its rot time is automatically the minimum over all sources. Running a separate BFS per source and taking minimums would compute the same answer at many times the cost.
What is the time complexity of the BFS solution to Rotting Oranges?
O(m·n) time and O(m·n) space for an m×n grid. The setup pass touches every cell once, and the BFS enqueues each cell at most once (cells are marked rotten the moment they're enqueued), doing four neighbor checks per dequeue. The queue can hold up to O(m·n) cells in the worst case, which is the space bound.
When does Rotting Oranges return -1, and when does it return 0?
It returns -1 when at least one fresh orange can never be reached — walled off by empty cells, or a grid with fresh oranges but no rotten source at all. It returns 0 when no time needs to pass: the grid has no fresh oranges to begin with (all rotten, all empty, or both). The fresh counter handles both: the loop only runs while fresh > 0, and the final return fresh === 0 ? minutes : -1 distinguishes success from an unreachable remainder.
Is queue.shift() a performance problem in JavaScript?
At this problem's constraints (grid up to 10×10), no — shift()'s O(n) cost is invisible. On large inputs it would degrade the algorithm to O((m·n)²), because every dequeue shifts the whole array. The standard fix is a read pointer: keep the array append-only, read queue[head++] instead of shifting, and the dequeue becomes O(1) with the same code shape.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.