The problem. Each cell of a grid is 0 (empty), 1 (a fresh orange) or 2 (a rotten orange). Every minute, each fresh orange next to a rotten one (up, down, left or right) becomes rotten. Return the number of minutes until no fresh orange is left — or -1 if some orange can never rot.
grid = [[2,1,1],
[1,1,0],
[0,1,1]] -> 4
grid = [[2,1,1],
[0,1,1],
[1,0,1]] -> -1 (the bottom-left orange is walled off)
grid = [[0,2]] -> 0 (no fresh oranges to begin with)BFS from one start spreads in rings: everything 1 step away, then 2 steps, then 3. Here the rot starts from every rotten orange at the same moment, so put all of them in the queue before the first step. Ring 1 is then every fresh orange next to any rotten one — exactly what rots in minute 1. Ring 2 is minute 2, and so on. The answer is the number of rings.
Think of it as one BFS from an imaginary source joined to every rotten orange. Never run one BFS per rotten orange: that repeats the same work for each of them, and they'd still have to be merged minute by minute.
A counter finishes the job. Count the fresh oranges at the start and subtract one each time an orange rots. If any are left when the rot stops spreading, some orange is walled off by empty cells: return -1.
Do exactly what the problem says. Each minute, scan the whole grid for fresh oranges with a rotten neighbour, then rot them all. Stop when a minute changes nothing.
Collect first, rot after the scan. If you rot during the scan, an orange that rotted this minute would pass the rot on in the same minute, and the count would come out too low.
const DIRS = [[-1, 0], [1, 0], [0, -1], [0, 1]]; function orangesRotting(grid) { const rows = grid.length, cols = grid[0].length; let minutes = 0; while (true) { const toRot = []; // fresh oranges next to a rotten one, this minute for (let r = 0; r < rows; r++) { for (let c = 0; c < cols; c++) { if (grid[r][c] !== 1) continue; 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] === 2) { toRot.push([r, c]); break; } } } } if (toRot.length === 0) break; // nothing changed: the spread has stopped for (const [r, c] of toRot) grid[r][c] = 2; // rot them together, after the scan minutes++; } for (const row of grid) if (row.includes(1)) return -1; // a fresh orange nobody can reach return minutes;}Time O((m · n)²), space O(m · n). Every minute rescans all m · n cells, and the rot can take up to about m · n minutes to crawl along a long winding line of oranges. Most of each scan finds nothing new.
Start with every rotten orange in a list. Each pass of the loop is one minute: every orange in the list rots its fresh neighbours, and those newly rotten oranges become the list for the next minute. Rot an orange the moment it's found, so no other orange can find it again.
Every rotten orange spreads at once; each pass of the loop is one minute. Try the walled-off example.
const DIRS = [[-1, 0], [1, 0], [0, -1], [0, 1]]; function orangesRotting(grid) { const rows = grid.length, cols = grid[0].length; let rotting = []; // the oranges spreading rot this minute let fresh = 0; for (let r = 0; r < rows; r++) { for (let c = 0; c < cols; c++) { if (grid[r][c] === 2) rotting.push([r, c]); // every rotten orange starts at once else if (grid[r][c] === 1) fresh++; } } let minutes = 0; while (rotting.length > 0 && fresh > 0) { const next = []; // the oranges that rot during this minute for (const [r, c] of rotting) { 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; // rot it now, so it's never counted twice fresh--; next.push([nr, nc]); } } } rotting = next; minutes++; } return fresh === 0 ? minutes : -1;}Time O(m · n), space O(m · n). The first scan reads every cell once, and after that each orange rots — and is looked at — exactly once, with 4 neighbour checks. The two lists only ever hold one ring of oranges.
Why fresh > 0 in the loop condition? Without it, the last minute's oranges would run one more pass that rots nothing, and minutes would end one too high.
Both give the same answer. The BFS only ever touches the oranges that are about to rot, instead of rescanning the whole grid every minute.