Problem overview
The method orangesRotting(grid) receives a grid of m rows and n columns, as an array of rows. Each cell holds 0 (empty), 1 (a fresh orange) or 2 (a rotten orange). Every minute, each fresh orange that touches a rotten one up, down, left or right becomes rotten. Diagonal neighbours don't count.
The method returns the number of minutes until no cell holds a fresh orange, or -1 if some orange can never rot.
In the first example, [[2,1,1],[1,1,0],[0,1,1]], the rot starts in the top-left corner and reaches the bottom-right corner in minute 4, so the answer is 4. In the second, [[2,1,1],[0,1,1],[1,0,1]], the orange in the bottom-left corner has empty cells above it and to its right, so the rot never reaches it and the answer is -1. For [[0,2]] no orange is fresh at the start, so the answer is 0.
Approach: breadth-first search from every rotten orange at once
A direct simulation scans the whole grid every minute. A long winding line of oranges lets the rot creep along one cell per minute, so the scans add up to O((m · n)²). The better view is that the rot spreads outward like a wave, and a breadth-first search (BFS) follows a wave naturally.
The search starts from every rotten orange at the same time: they all go into a queue before anything is processed. Then it works level by level. The oranges that rot in minute 1 are the first level, the oranges they rot are the second, and so on, so the number of levels is the number of minutes. A counter of fresh oranges, lowered each time one rots, tells at the end whether some orange never rotted. Each cell joins the queue at most once, because it is marked rotten the moment it is added.
The queue is an array with a head index that moves forward. Taking an element from the front with shift() would conceptually move every other element, while moving an index costs nothing.
Step by step
- Store the grid size:
rowsisgrid.lengthandcolsisgrid[0].length. Every row has the same length. - Create
queue, an empty array. It will hold[row, column]pairs of rotten oranges that are about to spread the rot. - Declare
freshwithlet, starting at 0. It counts the fresh oranges. - Scan the whole grid with two nested loops,
rover the rows andcover the columns. - Queue every rotten orange: if
grid[r][c] === 2, push[r, c]. All of them spread the rot in the first minute. - Count every fresh orange: if
grid[r][c] === 1, dofresh++. Empty cells are neither. - Define
directions, the four moves as[row change, column change]pairs: up, down, left and right. Each changes the row or the column by one, never both, so diagonals are excluded. - Declare
minutesat 0. When no orange is fresh at the start, no time passes. - Declare
headat 0: the index of the next orange to take fromqueue. - Write the outer
whileloop that runs whilehead < queue.lengthandfresh > 0. Each turn is one minute. Without thefresh > 0test, one extra minute would be counted after the last orange rots. - Count the minute with
minutes++. - Remember where this minute's level ends:
levelEndisqueue.length. The oranges fromheadup tolevelEndspread the rot in this minute, and the ones that rot now are added pastlevelEndfor the next minute. - Write the inner
whileloop overhead < levelEnd. One pass of it handles one level of the BFS. - Take the next orange: destructure
queue[head]intorowandcol, then dohead++. - Visit the four neighbours with
for...ofoverdirections, destructuring each move intodranddc, and computenextRowandnextCol. - Check the neighbour is inside the grid and holds
1. The bounds come first:&&stops at the first false part, so the grid is read only for a cell that exists. - Rot it: set it to 2, do
fresh--, and push[nextRow, nextCol]onto the queue. Marking it at once keeps any other orange from adding it a second time. - After the loops, return -1 if
fresh > 0, andminutesotherwise.
The solution in JavaScript
class Solution {
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++;
}
}
}
const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
let minutes = 0;
let head = 0;
while (head < queue.length && fresh > 0) {
minutes++;
const levelEnd = queue.length;
while (head < levelEnd) {
const [row, col] = queue[head];
head++;
for (const [dr, dc] of directions) {
const nextRow = row + dr;
const nextCol = col + dc;
if (nextRow >= 0 && nextRow < rows && nextCol >= 0 && nextCol < cols && grid[nextRow][nextCol] === 1) {
grid[nextRow][nextCol] = 2;
fresh--;
queue.push([nextRow, nextCol]);
}
}
}
}
if (fresh > 0) {
return -1;
}
return minutes;
}
}
The JavaScript details worth knowing:
- Destructuring.
const [row, col] = queue[head]unpacks a two-element array into two variables.for (const [dr, dc] of directions)does the same for each move. - Growing while reading. The queue grows during the loop, so
queue.lengthchanges. Copying it intolevelEndbefore the inner loop freezes the size of the current level. - The grid is changed in place. Arrays are passed by reference, so the method turns the caller's fresh oranges into 2s. After the first example, the grid is
[[2,2,2],[2,2,0],[0,2,2]]. - Short-circuit order. Reading
grid[-1][0]would throw aTypeError, becausegrid[-1]isundefined. Putting the bounds tests before the grid read avoids that. [[0]]and one-row grids.grid[0].lengthworks for any grid that has at least one row, and the statement guarantees that.
Complexity
Time: O(m · n). The first scan visits each cell once. In the search, each cell joins the queue at most once and looks at its four neighbours, so the work is a constant per cell.
Space: O(m · n). In the worst case every cell is an orange and passes through the queue. The head index never removes anything, so the queue keeps every pair until the method returns, which is still linear.
Edge cases and common mistakes
- No fresh orange at the start.
[[0, 2]]and[[2]]both return 0, and[[0]]does too. Thefresh > 0test stops the loop before any minute is counted. - Fresh orange and no rotten one.
[[1]]returns -1, because the queue is empty andfreshstays 1. - Unreachable oranges. In the second example the bottom-left orange stays fresh forever, so
freshis still above 0 when the queue runs out. - Counting an extra minute. Without
fresh > 0in the loop condition, the last rotten oranges would get one more turn, looking for neighbours that no longer exist, and the answer would be one too large. - Marking the orange too late. If the cell is set to 2 only when it is taken from the queue, two neighbours can both add it, and
freshgoes down twice for the same orange. - Treating diagonals as neighbours. With eight neighbours, the second example returns 2 instead of -1, because the bottom-left orange rots from the diagonal.
- Handling one rotten orange at a time. Running a separate search from each rotten orange measures the wrong thing: all of them rot their neighbours in the same minute, so they must share one queue.
Testing
[[2,1,1],[1,1,0],[0,1,1]]gives4.[[2,1,1],[0,1,1],[1,0,1]]gives-1.[[0,2]]gives0.[[1]]gives-1.[[1,2]]gives1.[[2,1,1,1,1]]gives4: one cell per minute along the row.
