Problem overview
The function oranges_rotting receives a grid of m rows and n columns, a Vec<Vec<i32>>. Each cell is 0 (empty), 1 (a fresh orange) or 2 (a rotten orange). Every minute, each fresh orange that is directly next to a rotten one (up, down, left or right, not diagonally) becomes rotten. The function 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 rot starts in the top-left corner and creeps outward one step per minute until it reaches the bottom-right corner. For [[2, 1, 1], [0, 1, 1], [1, 0, 1]] the answer is -1: the orange in the bottom-left corner has empty cells above it and to its right, so the rot never reaches it. For [[0, 2]] the answer is 0, because nothing is fresh at the start.
Approach: breadth-first search from all rotten oranges at once
A direct simulation scans the whole grid every minute, looking for fresh oranges next to rotten ones. On a long winding line of oranges the rot advances one cell per minute, so the number of minutes can be proportional to the number of cells, and the total work grows like (m · n)².
A breadth-first search (BFS) fits better. Rot spreads outward from its sources one step at a time, and BFS explores a graph the same way: first everything one step from the start, then everything two steps away, and so on. The twist is that there are several sources, every orange that is rotten at minute 0, so they all go into the queue before the search starts. The oranges that rot in minute 1 form the first level, the ones they rot form the second level, and so on. The number of levels is the number of minutes.
A counter of fresh oranges, lowered each time one rots, answers the -1 question. When the queue runs out and the counter is still above 0, those oranges are cut off from every rotten one.
Each cell enters the queue at most once, because it is marked rotten the moment it is added, so the work is proportional to the number of cells.
For the first example, after each minute the code has this many oranges in the queue (those that will spread the rot next) and this many fresh oranges left:
minute 1 queue_len=2 fresh=4
minute 2 queue_len=2 fresh=2
minute 3 queue_len=1 fresh=1
minute 4 queue_len=1 fresh=0
After minute 4 the loop stops with fresh = 0, and the answer is 4.
Step by step
- Make the grid mutable with
let mut grid = grid;. The search marks the oranges it rots, and the new binding takes over the vector the function received. - Store the dimensions:
rowsisgrid.len(), andcolsisgrid[0].len(), since every row has the same length. - Create the queue, a
VecDeque<(usize, usize)>. It holds the rotten oranges that are about to spread the rot, as (row, column) tuples.push_backandpop_frontboth run in constant time. - Create
freshat 0, the count of fresh oranges. - Scan the grid with
rover0..rowsand, inside it,cover0..cols. This first pass finds the starting sources and counts the fresh oranges. - Queue every rotten orange: if
grid[r][c] == 2, push(r, c). All of them spread the rot in the first minute, so they all start in the queue. - Count every fresh orange: if
grid[r][c] == 1, add 1 tofresh. Empty cells are neither. - Define the four directions as an array of
(i32, i32)tuples: up, down, left and right. Each move changes the row or the column by one, never both, so diagonals aren't neighbours. The moves arei32because they can be negative. - Start
minutesat 0. If no orange is fresh, no time passes. - Loop while the queue is not empty and
fresh > 0. Each turn is one minute. Without thefresh > 0test, the loop would count one extra minute after the last orange rots. - Add 1 to
minutes. A new minute starts. - Record the queue length in
level_size. These are the oranges that spread the rot this minute. Oranges that rot during the minute join the same queue but spread the rot only in the next one. - Repeat
level_sizetimes, with_as the unused loop variable. One pass of this loop handles one level of the BFS. - Pop the front tuple and unpack it into
(row, col). - Loop over the directions with the pattern
&(dr, dc). - Compute the neighbour as
i32values:row as i32 + drandcol as i32 + dc. - Check that the neighbour is inside the grid. In
i32, a step off the top or left edge is -1, which the check sees; as ausizeit would not exist. - Convert back to
usizeby shadowing the two names, now safe to index with. - Check for a fresh orange at that position.
- Rot it: set the cell to 2. Marking it immediately stops any other orange from rotting it again or queueing it twice.
- Subtract 1 from
fresh. - Push the neighbour onto the back of the queue, behind this minute's oranges.
- After the loop, return -1 if
fresh > 0. The queue ran out while oranges were still fresh. - Return
minutesas the last expression.
The solution in Rust
use std::collections::VecDeque;
impl Solution {
fn oranges_rotting(grid: Vec<Vec<i32>>) -> i32 {
let mut grid = grid;
let rows = grid.len();
let cols = grid[0].len();
let mut queue: VecDeque<(usize, usize)> = VecDeque::new();
let mut fresh = 0;
for r in 0..rows {
for c in 0..cols {
if grid[r][c] == 2 {
queue.push_back((r, c));
}
if grid[r][c] == 1 {
fresh += 1;
}
}
}
let directions: [(i32, i32); 4] = [(-1, 0), (1, 0), (0, -1), (0, 1)];
let mut minutes = 0;
while !queue.is_empty() && fresh > 0 {
minutes += 1;
let level_size = queue.len();
for _ in 0..level_size {
let (row, col) = queue.pop_front().unwrap();
for &(dr, dc) in &directions {
let next_row = row as i32 + dr;
let next_col = col as i32 + dc;
if next_row >= 0 && next_row < rows as i32 && next_col >= 0 && next_col < cols as i32 {
let (next_row, next_col) = (next_row as usize, next_col as usize);
if grid[next_row][next_col] == 1 {
grid[next_row][next_col] = 2;
fresh -= 1;
queue.push_back((next_row, next_col));
}
}
}
}
}
if fresh > 0 {
return -1;
}
minutes
}
}
The Rust details worth a closer look:
- Mutating the grid. A function parameter is immutable unless declared otherwise, and the signature takes
gridby value.let mut grid = grid;moves it into a mutable binding of the same name, so the original parameter can no longer be used. - Two integer types for positions. Vector indexes must be
usize, but a neighbour one step off the grid is -1, and ausizecan't hold that:0usize - 1panics in a debug build and wraps to a huge number in the-Obuilds the lessons use. So the arithmetic is done ini32, the bounds are checked, and only then is the position converted withas usize. - Shadowing.
let (next_row, next_col) = (next_row as usize, next_col as usize);declares new variables with the same names and the index type. The oldi32variables are no longer reachable inside that block. for &(dr, dc) in &directions. Iterating over a reference to the array yields references to the tuples. The pattern&(dr, dc)copies the two numbers out of each.pop_front()returns anOption.unwrap()is safe because the loop pops onlylevel_sizeelements, which the queue holds.- The inferred type of
freshandminutes. They start as0, and the function returnsminutesas ani32, so both arei32.
Complexity
Time: O(m · n). The first pass visits each cell once. In the search, each cell enters the queue at most once and looks at 4 neighbours, so the total is a constant times the number of cells.
Space: O(m · n). In the worst case, such as a grid full of rotten oranges, the queue holds every cell. The grid itself is changed in place.
Edge cases and common mistakes
- No fresh oranges.
[[0, 2]]returns 0, and so do[[2]]and[[0]]. Thefresh > 0test stops the loop before the first minute. - No rotten oranges.
[[1]]returns -1: the queue is empty and one orange is fresh. - Unreachable oranges. In the second example the BFS ends with
fresh = 1, and the function returns -1. The loop does run a minute in which nothing rots, but the -1 return hides it. - A single row.
[[2, 1, 1, 1, 1]]takes 4 minutes: the rot moves one cell per minute along the row. - Counting minutes per orange. Adding 1 for every orange taken from the queue counts oranges, not minutes. That is why the loop takes exactly
level_sizeoranges and then adds one minute for the whole level. - Not marking at once. If the cell were marked only when popped, the same orange could be queued by several neighbours and
freshwould go down several times for it. - Diagonal spread. Adding diagonal moves to
directionswould change the answers: the bottom-left orange of the second example would rot.
Testing
[[2, 1, 1], [1, 1, 0], [0, 1, 1]]gives 4.[[2, 1, 1], [0, 1, 1], [1, 0, 1]]gives -1.[[0, 2]]gives 0.[[1]]gives -1.[[2]]gives 0.[[2, 1, 1, 1, 1]]gives 4.
