Problem overview
The function size_of_islands receives a grid of integers, where 1 is land and 0 is water. An island is a group of land cells connected horizontally or vertically (diagonal neighbors don't count). The function returns a vector with the size of each island, in any order.
Take this grid, which has four rows and five columns:
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1
It holds three islands: a 2-by-2 block of size 4, a single cell of size 1, and a pair of cells of size 2. The function produces [4, 1, 2], the sizes in the order the islands are found when scanning row by row.
Approach: scan, then flood each island
Scan the grid cell by cell. Whenever a land cell turns up, a new island has been found. Then a depth-first search "floods" it: it visits that cell and every land cell connected to it, counting them as it goes. Flooding is also how the scan avoids counting an island twice: each visited land cell is turned into water, so the scan and the search never see it again.
Turning cells to water means the grid itself serves as the visited record, so no extra structure is needed. The function takes the grid by value (mut grid), so it changes its own copy only.
The search is naturally recursive. A call for cell (row, col) returns 0 if the cell is outside the grid or isn't land. Otherwise it turns the cell to water and returns 1 plus the results of the four neighboring calls. On the example, the first land cell at the top left starts a search that returns 4. The next land cell found by the scan is at row 2, column 2, and its search returns 1. The last search starts at row 3, column 3, and returns 2.
Step by step
- Create
resultas an empty vector withlet mut. Its element type is inferred from what is pushed later. - Store the number of rows in
rows. If it is 0, returnresultright away: an empty grid has no islands, and reading its first row would panic. An early exit needs thereturnkeyword. - Store the number of columns, the length of the first row, in
cols. - Loop over the row index
ifrom 0 up to but not includingrows. - Loop over the column index
jthe same way, inside it. - Check for land:
grid[i][j] == 1. Rust has no truthy integers, so the comparison is written out. - Measure the island. Call
Self::dfs(&mut grid, i as i32, j as i32)and store the answer insize. The helper changes the grid, so it gets a mutable borrow. The coordinates are signed because the helper steps to neighbors likerow - 1, which can be negative. - Push
sizeontoresult. - Return
resultas the final expression. - Declare
dfswith a&mut Vec<Vec<i32>>grid andi32coordinatesrowandcol, returning ani32. - Store the dimensions as
i32inrowsandcols, so they can be compared with coordinates that may be negative. - Return 0 for cells that count for nothing: outside the grid, or not land. The bounds checks come first, joined with
||, so the grid is indexed only once the coordinates are known to be valid. - Mark the cell as water by setting it to 0.
- Start
countat 1, for the current cell. - Loop over the four directions, an array of
(dr, dc)pairs: up, down, left and right. Thei32suffixes on the first pair fix the type of the whole array. - Add the neighbor's search to
count:Self::dfs(grid, row + dr, col + dc). - Return
count.
The solution in Rust
impl Solution {
fn dfs(grid: &mut Vec<Vec<i32>>, row: i32, col: i32) -> i32 {
let rows = grid.len() as i32;
let cols = grid[0].len() as i32;
if row < 0 || row >= rows || col < 0 || col >= cols || grid[row as usize][col as usize] != 1
{
return 0;
}
grid[row as usize][col as usize] = 0;
let mut count = 1;
for (dr, dc) in [(-1i32, 0i32), (1, 0), (0, -1), (0, 1)] {
count += Self::dfs(grid, row + dr, col + dc);
}
count
}
fn size_of_islands(mut grid: Vec<Vec<i32>>) -> Vec<i32> {
let mut result = Vec::new();
let rows = grid.len();
if rows == 0 {
return result;
}
let cols = grid[0].len();
for i in 0..rows {
for j in 0..cols {
if grid[i][j] == 1 {
let size = Self::dfs(&mut grid, i as i32, j as i32);
result.push(size);
}
}
}
result
}
}
The Rust details worth a closer look:
- Why the signed coordinates. A neighbor of row 0 is row
-1. In ani32that is a number the bounds check can reject. In ausizeit can't exist: subtracting 1 from ausizethat holds 0 panics in a debug build and wraps around to a huge number in a build with optimizations. Converting withas usizeonly after the bounds check avoids both. - Short-circuit order.
||stops at the first true condition. The testgrid[row as usize][col as usize] != 1is last, so it runs only for coordinates already known to be inside the grid. - Passing the grid down. In
size_of_islands,&mut gridlends the grid to the helper for the duration of the call. Insidedfs,gridis already a mutable reference, so the recursive call passes it on as it is. - Looping over an array of tuples. In edition 2021,
for (dr, dc) in [...]iterates the array by value and destructures each pair. - The inferred
resulttype.Vec::new()has no element type untilresult.push(size)shows it is aVec<i32>, which also matches the return type. - Final expressions.
countandresulthave no semicolon, so they are the returned values. Adding a semicolon would make the function return nothing, and the compiler would reject it.
Complexity
Time: O(rows · cols). The scan visits each cell once. Each land cell is flooded once, because it becomes water immediately, and each call does a constant amount of work apart from its recursive calls.
Space: O(rows · cols) in the worst case. The recursion goes as deep as the longest chain of land cells the search follows. A grid that is all land can make that chain as long as the whole grid. A 100-by-100 grid of land returns [10000] without trouble, but a much larger grid could exhaust the stack, and an explicit stack or a queue would avoid that.
Edge cases and common mistakes
- An empty grid. An empty vector returns
[]. Without therows == 0check,grid[0]would panic. - No land.
[[0, 0]]returns[]. - Diagonals don't connect. The grid
[[1,0,1],[0,1,0],[1,0,1]]has five islands of size 1 each. - Counting an island twice. Forgetting to set the cell to 0 before recursing makes neighbors call each other forever, so the program runs out of stack.
- Checking the bounds after indexing. Reading
grid[row as usize][col as usize]before the range checks panics on the first neighbor outside the grid. - The input is consumed. After the function runs, its copy of the grid is all water. Callers that need the grid afterwards must pass a clone.
Testing
- The 4-by-5 grid above gives
[4, 1, 2]. [[1,1,1,1,0],[1,1,0,1,0],[1,1,0,0,0],[0,0,0,0,0]]gives[9].[[1,0,1],[0,1,0],[1,0,1]]gives[1, 1, 1, 1, 1].[]gives[].
