Problem overview
The method orangesRotting receives a grid of integers, an Array[Array[Int]]. Each cell is 0 (empty), 1 (a fresh orange) or 2 (a rotten orange). Every minute, each fresh orange that has a rotten one directly above, below, left or right of it 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.
In the first example, the grid is [[2, 1, 1], [1, 1, 0], [0, 1, 1]]. The rot spreads from the corner: two oranges rot in minute 1, more in each following minute, and after minute 4 nothing is fresh, 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 an empty cell above it and another to its right. Rot never reaches it, so the answer is -1. For [[0, 2]] there is nothing fresh at the start, and the answer is 0.
Approach: breadth-first search, one level per minute
Simulating the grid minute by minute and scanning every cell each time can cost O((m * n)^2): picture a long winding line of oranges that the rot creeps along one cell per minute. A breadth-first search (BFS) does the work in O(m * n).
The search starts from every rotten orange at once, so they all go into a queue before it begins. The oranges that rot in minute 1 form the first level, the ones they rot form the second level, and so on. Each level of the BFS is one minute, so the number of levels is the answer.
A counter of fresh oranges, lowered each time one rots, tells at the end whether some orange never rotted: if it is above 0 when the queue runs out, no chain of oranges links those oranges to a rotten one.
The loop stops as soon as the counter reaches 0. Without that, it would count one more minute after the last orange rots, while the last rotten oranges look for fresh neighbours that are gone.
Step by step
- Read the size.
rowsisgrid.lengthandcolsisgrid(0).length. Every row has the same length, so the first row gives the column count. Arrays are indexed with parentheses in Scala. - Create the queue, a
mutable.Queue[(Int, Int)](). It will hold (row, column) tuples of the rotten oranges that are about to spread the rot.enqueueadds at the back anddequeue()takes from the front. - Declare
freshas avarstarting at 0. - Loop over the rows with
r <- 0 until rows, and inside it loop over the columns withc <- 0 until cols. This first pass finds the oranges that start rotten and counts the fresh ones. - Enqueue every rotten orange: if
grid(r)(c) == 2, enqueue(r, c). - Count every fresh orange: if
grid(r)(c) == 1, add 1 tofresh. Empty cells are neither and are left alone. - List the four moves as an array of (row change, column change) tuples:
(-1, 0)up,(1, 0)down,(0, -1)left and(0, 1)right. - Declare
minutesas avarstarting at 0. If nothing is fresh at the start, no time passes. - Loop while there is something to do:
queue.nonEmpty && fresh > 0. Each turn of this loop is one minute, so start it withminutes += 1. - Freeze the level. Store
queue.sizeinlevelSize. Oranges that rot during this minute join the same queue, but they spread rot only in the next minute, so this minute handles exactlylevelSizeoranges. - Process the level with
_ <- 0 until levelSize, where_stands for a loop variable that isn't used. Take the front orange withdequeue()and unpack it asval (row, col). - Visit the four neighbours with
(dr, dc) <- directions. ComputenextRow = row + drandnextCol = col + dc. - Check the neighbour: it must be inside the grid, and
grid(nextRow)(nextCol)must be 1. The bounds come first, so the grid is read only for a cell that exists. - Rot it: set that cell to 2 right away, so no other orange rots it again or queues it twice. Subtract 1 from
fresh, and enqueue(nextRow, nextCol)behind this minute's oranges. - After the loop, if
fresh > 0, return -1: the queue ran out while some oranges were still fresh. - Finish with
minutesas the last expression.
The solution in Scala
class Solution {
def orangesRotting(grid: Array[Array[Int]]): Int = {
val rows = grid.length
val cols = grid(0).length
val queue = mutable.Queue[(Int, Int)]()
var fresh = 0
for (r <- 0 until rows) {
for (c <- 0 until cols) {
if (grid(r)(c) == 2) {
queue.enqueue((r, c))
}
if (grid(r)(c) == 1) {
fresh += 1
}
}
}
val directions = Array((-1, 0), (1, 0), (0, -1), (0, 1))
var minutes = 0
while (queue.nonEmpty && fresh > 0) {
minutes += 1
val levelSize = queue.size
for (_ <- 0 until levelSize) {
val (row, col) = queue.dequeue()
for ((dr, dc) <- directions) {
val nextRow = row + dr
val nextCol = col + dc
if (nextRow >= 0 && nextRow < rows && nextCol >= 0 && nextCol < cols && grid(nextRow)(nextCol) == 1) {
grid(nextRow)(nextCol) = 2
fresh -= 1
queue.enqueue((nextRow, nextCol))
}
}
}
}
if (fresh > 0) {
return -1
}
minutes
}
}
The Scala details worth a closer look:
mutable.Queue. The lesson's code uses the mutable queue fromscala.collection.mutable, which the lesson already makes available. In a file of your own, addimport scala.collection.mutable. Callingdequeue()on an empty queue throws aNoSuchElementException("empty collection"), which the loop condition prevents here.- Tuples.
(r, c)is a pair ofInts, written(Int, Int)as a type. The extra parentheses inqueue.enqueue((r, c))are the tuple itself inside the call's own parentheses. - Destructuring.
val (row, col) = queue.dequeue()unpacks the tuple into two names.for ((dr, dc) <- directions)does the same for each move. &&short-circuits. It stops at the first false part, sogrid(nextRow)(nextCol)is read only after the four bounds checks pass. Readinggrid(-1)would throwArrayIndexOutOfBoundsException.- The grid changes in place. Arrays are mutable and passed by reference, so after the call the caller's grid shows the result. For the first example it ends as
2 2 2 / 2 2 0 / 0 2 2. For the second, the unreachable orange is still 1, and the grid ends as2 2 2 / 0 2 2 / 1 0 2. - Return.
return -1is an early exit from inside anif. The last expression,minutes, is the ordinary result.
Complexity
Time: O(m * n). The first pass visits every cell once. Each cell joins the queue at most once, because it is marked rotten when it is queued, and each dequeued cell looks at four neighbours.
Space: O(m * n). In the worst case the queue holds a large share of the cells, for example a grid that starts almost entirely rotten.
Edge cases and common mistakes
- No fresh oranges.
[[0, 2]]and[[0]]and[[2]]all give 0. The loop never starts. - Only fresh oranges.
[[1]]gives -1: the queue is empty, so nothing can ever rot. - A fresh orange cut off by empty cells. The second example gives -1 because
freshis still 1 when the queue runs out. - Several rotten oranges at the start.
[[1, 2, 1, 1, 2, 1, 1]]gives 2. Starting from all rotten oranges at once is what makes the minutes count right. Running one search per rotten orange would count the distances separately. - A long row.
[[2, 1, 1, 1, 1]]gives 4: one orange rots per minute. - Counting one minute too many. Without
fresh > 0in the loop condition, the last level is processed again after the final orange rots, and the answer is one larger. - Not marking the neighbour right away. Two rotten oranges could then both queue the same neighbour, and
freshwould go down twice for it. - Diagonal neighbours. Only the four moves in
directionsspread rot.
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, 2]]gives1.[[2, 1, 1, 1, 1]]gives4.
