Problem overview
The function orangesRotting receives a grid of m rows and n columns, a slice of rows where each row is a slice of ints. Each cell holds 0 (empty), 1 (a fresh orange) or 2 (a rotten orange). Every minute, each fresh orange directly above, below, left or right of a rotten one becomes rotten. Diagonal contact doesn't count. The function returns the number of minutes until no fresh orange is left, 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 creeps along the oranges. After minute 4 the last one, in the bottom-right corner, has rotted, so the answer is 4. In [[2,1,1],[0,1,1],[1,0,1]] the orange in the bottom-left corner has empty cells above and to its right, so the rot never reaches it, and the answer is -1. In [[0,2]] there is nothing fresh at the start, so the answer is 0.
Approach: breadth-first search from every rotten orange
The simplest idea simulates the grid minute by minute and scans every cell each time. A long winding line of oranges, where the rot advances one cell per minute, makes that cost about (m · n)² overall. The statement asks for O(m · n).
The key is to see the process as a breadth-first search (BFS). The oranges that are rotten at minute 0 are the sources. The fresh oranges next to them rot in minute 1: that is the first level of the search. The oranges next to those rot in minute 2, the second level, and so on. The number of levels is the number of minutes. Because all rotten oranges spread at the same time, the search must start from all of them at once: put every initial rotten orange in the queue before the loop begins.
A counter of fresh oranges tells the story at the end. Every time an orange rots, subtract 1. If the counter is 0 when the search is over, all of them rotted. If it is above 0, no chain of oranges connected those to a rotten one, and the answer is -1.
Each cell joins the queue at most once, because it is turned rotten the moment it is added, so the whole search costs O(m · n).
Step by step
- Store the grid size.
rowsislen(grid)andcolsislen(grid[0]), since every row has the same length. - Create
queueas an empty[][2]int: a slice of two-int arrays, each holding a row and a column. A slice works as a queue becauseappendadds at the back and reslicing drops the front. - Create
freshas 0 to count the fresh oranges. - Scan all rows and columns with two nested loops, to find the starting state.
- Queue each rotten orange. Where
grid[r][c] == 2, append[2]int{r, c}. They all spread the rot in the first minute. - Count each fresh orange. Where
grid[r][c] == 1, dofresh++. Empty cells are ignored. - Write
directionsas the four moves,{-1, 0}up,{1, 0}down,{0, -1}left and{0, 1}right. Each changes the row or the column by one, never both, so diagonal cells aren't neighbours. - Create
minutesas 0. If nothing is fresh at the start, 0 is the answer. - Loop while the queue is non-empty and
freshis above 0. Each turn of this loop is one minute. Go has nowhile, so aforwith only a condition does the job. - Add 1 to
minutes. A new minute begins. - Record
levelSizeaslen(queue). These are the oranges that spread the rot this minute. The oranges that rot during the minute join the same queue, but wait for the next minute. - Loop
levelSizetimes. One pass of this loop is one level of the BFS. - Take the front orange with
cell := queue[0]and drop it withqueue = queue[1:]. - Unpack it into
row, col := cell[0], cell[1]. - Loop over
directionswithrange, ignoring the index with_. - Compute the neighbour as
nextRowandnextCol. - Check that the neighbour is on the grid and fresh. The bounds come first, because
&&stops at the first false part, so the grid is read only for a cell that exists. - Rot it by setting
grid[nextRow][nextCol] = 2right away, so no other orange rots it again or queues it a second time. - Decrease
freshwithfresh--. - Append the new rotten orange to the back of the queue, to spread the rot next minute.
- After the loop, return -1 if
freshis above 0. The queue ran out while some oranges were still fresh. - Otherwise return
minutes.
The solution in Go
func orangesRotting(grid [][]int) int {
rows := len(grid)
cols := len(grid[0])
queue := [][2]int{}
fresh := 0
for r := 0; r < rows; r++ {
for c := 0; c < cols; c++ {
if grid[r][c] == 2 {
queue = append(queue, [2]int{r, c})
}
if grid[r][c] == 1 {
fresh++
}
}
}
directions := [][2]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
minutes := 0
for len(queue) > 0 && fresh > 0 {
minutes++
levelSize := len(queue)
for i := 0; i < levelSize; i++ {
cell := queue[0]
queue = queue[1:]
row, col := cell[0], cell[1]
for _, d := range directions {
nextRow := row + d[0]
nextCol := col + d[1]
if nextRow >= 0 && nextRow < rows && nextCol >= 0 && nextCol < cols && grid[nextRow][nextCol] == 1 {
grid[nextRow][nextCol] = 2
fresh--
queue = append(queue, [2]int{nextRow, nextCol})
}
}
}
}
if fresh > 0 {
return -1
}
return minutes
}
The Go details worth a closer look:
[2]intis an array, not a slice. It has exactly two ints, and it is a value type, so each queue entry is a small self-contained pair.[][2]int{{-1, 0}, {1, 0}, ...}lets Go infer the inner[2]inttype for each pair.- A slice as a queue.
queue = queue[1:]drops the front by moving the slice's start forward. No elements are copied.appendadds at the back and reallocates when there is no room left. - The grid is changed in place. A slice of slices shares its memory with the caller, so setting cells to 2 changes the caller's grid. In the first example the caller's grid ends as
[[2 2 2] [2 2 0] [0 2 2]]. Copy the grid first if you still need the original. - Short-circuit
&&. In Go, indexing outside a slice panics. The condition tests the bounds beforegrid[nextRow][nextCol], so that read never happens for an off-grid cell. forwith a condition only.for len(queue) > 0 && fresh > 0 { ... }is Go'swhile.
Complexity
Time: O(m · n). The first pass visits every cell once. In the search each cell enters the queue at most once, and each one is examined for 4 neighbours, so the work is a constant per cell.
Space: O(m · n). In the worst case, such as a grid that is all rotten, the queue holds every cell. Besides that the code uses a few integers.
Edge cases and common mistakes
- No fresh oranges.
[[0, 2]]and[[0]]return 0, and so does[[2]]. The loop condition is false at once. - Fresh oranges and no rotten one.
[[1]]returns -1: the queue is empty, the loop never runs, andfreshis 1. - Isolated oranges.
[[2, 0, 1]]returns -1: the empty cell between them blocks the rot, and diagonal contact doesn't count either. - Counting one minute too many. Without
fresh > 0in the loop condition, the last rotten oranges would run one more minute that does nothing. The first example would return 5 instead of 4, and[[0, 2]]would return 1 instead of 0. The check stops the loop right after the last orange rots. - Several rotten oranges at the start.
[[2, 2], [1, 1], [0, 0]]returns 1: both fresh oranges are next to a rotten one, so they rot in the same minute. Starting the search from one source at a time would give the wrong answer, because the sources spread at once. - Rotting a cell late. If the cell is marked when it is taken from the queue rather than when it is added, the same orange can be queued several times and the counter goes wrong.
- Reading before checking bounds. Putting
grid[nextRow][nextCol] == 1before the bounds tests panics with an index out of range on the border. - A line of oranges.
[[2, 1, 1, 1, 1]]takes 4 minutes, one per fresh orange, because the rot moves one cell per minute.
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,0,1]]gives-1.[[1,2]]gives1.[[2,1,1,1,1]]gives4.[[2,2],[1,1],[0,0]]gives1.
