Problem overview
The function num_islands receives a grid of 1s (land) and 0s (water) as a Vec<Vec<i32>>. It returns how many islands the grid contains. An island is a group of land cells connected horizontally or vertically; diagonal neighbours don't connect. The edges of the grid are treated as water.
In the first example the grid is:
1 1 1 1 0
1 1 0 1 0
1 1 0 0 0
0 0 0 0 0
All the 1s are linked, so the answer is 1. In the second example:
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1
there is a 2×2 block, a lone cell at row 2 and a pair at the bottom right. The lone cell doesn't touch the pair, because it only meets it diagonally, so the answer is 3.
Approach: count a start, then erase the island
Scan the grid cell by cell. The first land cell you meet in a new island is the one that gets counted. The difficulty is not counting the other cells of the same island again.
The fix is to erase the island as soon as you count it. When the scan finds a 1 that nothing has erased, it adds one to the result and starts a depth-first search (DFS) from that cell. The DFS turns the cell into 0, then visits each of its four neighbours, which turn their own land neighbours into 0, and so on, until the whole island is water. When the scan continues, every remaining 1 must belong to an island that hasn't been seen.
Overwriting the grid works as the "visited" marker, so no extra structure is needed. The cost is that the input is modified. That is fine here, because the function takes ownership of the grid (the mut grid parameter), so the caller never sees the changes.
Step by step
- Declare
resultwithlet mut, starting at 0. - Read the number of rows and handle an empty grid. If
grid.len()is 0, there are no islands, so return 0. This also makesgrid[0]safe in the next step. - Read the number of columns as
grid[0].len(). - Loop over every cell with two nested
forloops over0..rowsand0..cols. - When
grid[i][j]is 1, add 1 toresultand callSelf::dfs(&mut grid, i, j). The cell belongs to an island nothing has erased yet. - Return
resultafter the loops, as the final expression. - Write
dfs. It takes the grid by mutable reference plus arowand acol, and returns nothing. - Stop at water. If the cell is 0, it is water or already erased, so return.
- Erase the cell by setting it to 0 before exploring its neighbours. If this were done after the recursive calls, two neighbouring cells could keep calling each other forever.
- Read the grid's dimensions inside
dfs, so the moves can be checked against them. - Visit the four neighbours, but only when each one exists:
row > 0for up,row + 1 < rowsfor down,col > 0for left andcol + 1 < colsfor right.
The solution in Rust
impl Solution {
fn dfs(grid: &mut Vec<Vec<i32>>, row: usize, col: usize) {
if grid[row][col] == 0 {
return;
}
grid[row][col] = 0;
let rows = grid.len();
let cols = grid[0].len();
if row > 0 {
Self::dfs(grid, row - 1, col);
}
if row + 1 < rows {
Self::dfs(grid, row + 1, col);
}
if col > 0 {
Self::dfs(grid, row, col - 1);
}
if col + 1 < cols {
Self::dfs(grid, row, col + 1);
}
}
fn num_islands(mut grid: Vec<Vec<i32>>) -> i32 {
let mut result = 0;
let rows = grid.len();
if rows == 0 {
return 0;
}
let cols = grid[0].len();
for i in 0..rows {
for j in 0..cols {
if grid[i][j] == 1 {
result += 1;
Self::dfs(&mut grid, i, j);
}
}
}
result
}
}
The Rust details worth a closer look:
mut gridin the signature. The parameter owns its vector (the caller's vector is moved in), andmutlets the function change it. The caller can't use its own variable afterwards.&mut gridversusgrid. Innum_islandsyou lend the grid with&mut grid. Insidedfs,gridalready is a&mut Vec<Vec<i32>>, so the recursive calls pass it on as it is. Rust reborrows it for each call, so the same reference can be passed several times in a row.usizeand the neighbour checks. Indices areusize, which can't be negative. Ifrowis 0,row - 1is not -1: in an optimized build it wraps to the largestusize, and indexing with it panics with "index out of bounds". In a debug build the subtraction itself panics. That is whyrow > 0is checked before subtracting. The checkrow + 1 < rowsis written as an addition so that no subtraction can underflow.Self::dfs.dfshas noselfparameter, so it is an associated function, called through the type.- Double indexing.
grid[row][col]indexes the outer vector, then the inner one. Both are bounds-checked. - No return value in
dfs. A function without->returns(), and the barereturn;exits early.
Complexity
Time: O(rows × cols). The scan visits each cell once. The DFS also touches each land cell once, because it erases a cell the first time it reaches it, and every later arrival returns immediately. Each cell is therefore handled a constant number of times in total.
Space: O(rows × cols) in the worst case. The grid is modified in place, so there is no visited array. The recursion's call stack is the extra cost: on a grid that is all land, the depth can reach the number of cells.
Edge cases and common mistakes
- Empty grid.
vec![]returns 0. Without the early return,grid[0]would panic. - All water. A 2×2 grid of zeros returns 0.
- One big island. A 2×3 grid of 1s returns 1.
- Diagonals don't connect. The grid
[[1, 0], [0, 1]]has 2 islands, and a 3×3 checkerboard with land at the corners and the centre has 5. - Marking after recursing. Erasing the cell after the four recursive calls makes neighbouring cells visit each other again and again until the stack overflows.
- Unchecked moves. Skipping the bounds checks causes a panic at the first land cell on an edge.
- Very deep recursion. A huge single island, such as a 1,000 × 1,000 grid of land, can exhaust the usual 8 MB stack of a program's main thread, because each cell adds a stack frame. For grids that large, an explicit stack stored in a
Vecis safer.
Testing
- The first example grid gives
1, and the second gives3. [[1]]gives1.[[0, 0], [0, 0]]gives0.[[1, 0, 1, 0, 1]]gives3.[[1, 0, 1], [0, 1, 0], [1, 0, 1]]gives5.
