Problem overview
The method orangesRotting receives a grid of m rows and n columns, an array of rows of integers. Each cell is 0 (empty), 1 (a fresh orange) or 2 (a rotten orange). Every minute, each fresh orange that is directly up, down, left or right of a rotten one becomes rotten. Diagonal neighbours don't count. The method returns the number of minutes until no fresh orange is left, or -1 if some orange can never rot.
For the grid [[2, 1, 1], [1, 1, 0], [0, 1, 1]] the answer is 4. The two oranges next to the rotten corner rot in minute 1, the oranges next to those in minute 2, and so on, until the bottom right corner rots in minute 4. For [[2, 1, 1], [0, 1, 1], [1, 0, 1]] the answer is -1: the bottom left orange has an empty cell above it and to its right, and rot doesn't spread diagonally. For [[0, 2]] the answer is 0, since nothing is fresh to begin with.
Approach: spread level by level from every rotten orange
The direct way is to simulate: each minute, scan every cell and rot the fresh ones next to a rotten one. With a long winding line of oranges the rot creeps one cell per minute, so there can be about m · n minutes with a scan of m · n cells each: O((m · n)²). The statement allows O(m · n).
A breadth-first search (BFS) fits, because rot spreads outward at one step per minute, which is exactly how BFS moves outward one level at a time. There is a twist: the search doesn't start from one cell but from all the oranges that are rotten at minute 0, all in the queue at once. Then:
- the oranges that rot in minute 1 are the first level, and the oranges they rot are the second, so the number of levels processed is the number of minutes;
- a count of fresh oranges, lowered each time one rots, tells at the end whether some never rotted;
- each cell joins the queue at most once, because it is marked rotten the moment it is added.
Here is the first example after each minute:
minute 1 minute 2 minute 3 minute 4
2 2 1 2 2 2 2 2 2 2 2 2
2 1 0 2 2 0 2 2 0 2 2 0
0 1 1 0 1 1 0 2 1 0 2 2
Step by step
- Store the size.
rowsisgrid.lengthandcolsisgrid[0].length, since every row has the same length. - Create
queue, an emptynumber[][]that will hold[row, column]pairs of rotten oranges that are about to spread the rot. - Declare
freshat 0, the number of fresh oranges. - Scan the whole grid with two nested loops, over
randc. - Queue every rotten orange. If
grid[r][c] === 2, push[r, c]. All oranges that are rotten at the start spread rot in minute 1. - Count every fresh orange. If
grid[r][c] === 1, dofresh++. Empty cells are neither. - List the four moves in
directions:[-1, 0],[1, 0],[0, -1]and[0, 1]. Each changes the row or the column by one, never both. - Declare
minutesat 0. With no fresh orange at the start, no time passes. - Declare
headat 0, the index of the next orange to take fromqueue. Moving an index forward takes an orange off the front without removing anything, whereasshift()on an array may move the other elements. - Start the minute loop:
while (head < queue.length && fresh > 0). Each turn is one minute. Withoutfresh > 0, the loop would count one extra minute after the last orange rots. - Add 1 to
minutes. If the queue's oranges rot nothing, the queue runs out and the answer is -1 anyway. - Fix where this minute's oranges end:
levelEndisqueue.lengthright now. Oranges that rot during this minute are added pastlevelEndand spread the rot in the next minute. - Process one level with an inner
while (head < levelEnd). This loop is the key to counting minutes. - Take the next orange:
const [row, col] = queue[head];thenhead++. - Visit each neighbour. For each
[dr, dc]indirections, computenextRowandnextCol. - Check the neighbour. It must be inside the grid and hold a fresh orange. The bounds come first:
&&stops at the first false part, so the grid is read only for a cell that exists. - Rot it: set the cell to 2, subtract 1 from
fresh, and push[nextRow, nextCol]to the back of the queue. Marking it at once means it can't be rotted or queued again. - After the loops, return -1 if
freshis still above 0, andminutesotherwise.
The solution in TypeScript
class Solution {
orangesRotting(grid: number[][]): number {
const rows = grid.length;
const cols = grid[0].length;
const queue: number[][] = [];
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;
}
}
A few TypeScript details:
- Destructuring.
const [row, col] = queue[head];unpacks a two-element array into two constants, andfor (const [dr, dc] of directions)does the same for each move. The types come from the arrays:queueis anumber[][], sorowandcolare numbers. - An array as a queue.
pushadds at the end in constant time. Theheadindex stands in for removing from the front, so the queue only ever grows, and its length stays belowm · nbecause every cell enters at most once. - The grid is changed. The method writes 2 into
gridas oranges rot, so the caller's array holds the final state afterwards. Copy the grid first if the original is still needed. - Strict equality.
===compares the numbers without any conversion. The grid holds numbers, so it behaves the same as==here.
Complexity
Time: O(m · n). The first scan visits every cell once. In the search, each cell joins the queue at most once and looks at its 4 neighbours.
Space: O(m · n). In the worst case, nearly every cell is rotten and sits in the queue. The grid itself is changed in place and needs no extra copy.
Edge cases and common mistakes
- No fresh orange.
[[0, 2]],[[0]]and[[2]]all give 0. The minute loop never starts becausefreshis 0. - Fresh oranges but no rotten one.
[[1]]gives -1: the queue is empty from the start, sofreshstays above 0. - Unreachable oranges.
[[2, 1, 0, 1]]gives -1: the empty cell cuts the row, and the orange on the far side of it never rots. - An off-by-one in the minutes. Without
fresh > 0in the loop condition, one more minute is counted after the last orange rots, because the newest oranges are still in the queue. For the first example the loop would return 5. - Not marking at once. If a rotted cell isn't set to 2 until it is taken from the queue, two neighbours can both add it, and
freshgoes down twice for the same orange. - Counting levels wrongly. Without
levelEnd, the loop can't tell where one minute ends and the next begins, so the oranges rotted this minute would be mixed up with the ones that spread the rot, andminutescouldn't be counted. - Diagonals. Adding moves like
[1, 1]todirectionsmakes oranges rot faster than the problem allows. - Reading before checking bounds.
grid[nextRow][nextCol]withnextRowequal to -1 readsgrid[-1], which isundefined, and indexing that throws aTypeError. The bounds checks come first for this reason.
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.[[2, 1, 1, 1, 1]]gives4.[[2, 1, 0, 1]]gives-1.
