Problem overview
The method NumIslands receives a grid of 0s and 1s as an int[,]. A 1 is land, a 0 is water. An island is a group of land cells connected horizontally or vertically. The method returns how many islands the grid has.
In the first example, every 1 is linked to the others through side-by-side neighbours, so there is one island. In the second example, the 1s in the top-left 2x2 block form one island, the lone 1 in row 2 forms another, and the two 1s at the bottom right form a third. The answer is 3. The lone 1 touches the top-left block only at a corner, and diagonal contact does not connect cells.
Approach: count, then erase the island
Scan the grid cell by cell. The first time you meet a land cell, you have found a new island. The difficulty is that the same island has many cells, and you must not count it again for each of them.
The fix is to erase an island as soon as you count it. When the scan reaches a 1, add one to the result, then run a depth-first search (DFS) from that cell. The search visits every land cell connected to it and sets each to 0. When the scan continues, the rest of that island is already water, so it is never counted a second time. Each island adds exactly 1 to the result, at its first cell in scan order.
The DFS itself is a recursive function. For one cell it asks: is this cell land inside the grid? If not, stop. If so, turn it into water, then do the same for the four neighbours: up, down, left and right.
Step by step
The lesson builds the main method first and assumes a helper exists, then writes the helpers.
- Declare
resultas anintset to 0. It counts the islands found so far. - Loop over the rows. A two-dimensional array
int[,]reports its row count withgrid.GetLength(0). - Loop over the columns inside it, up to
grid.GetLength(1). Don't usegrid.Lengthfor either bound: for anint[,]it is the total number of cells. - Test whether
grid[i, j]is 1. A rectangular array is indexed with one pair of brackets and a comma. - Increment
resultinside theif. This is the only place the count changes. A land cell reached here was not erased by an earlier search, so it belongs to a new island. - Call
Dfs(grid, i, j)to erase the island, and returnresultafter the loops. - Write
Dfs. It takes the grid, a row and a column, and returns nothing. - Stop at invalid cells. Ask a helper,
IsValidCell, whether the cell is on the grid and is land. If not,returnimmediately. Water and off-grid neighbours both end the search in that direction. - Mark the cell as water by setting it to 0 before recursing. Without this, two neighbours would keep sending the search back to each other forever.
- Describe the four moves as pairs of (row change, column change): up
(-1, 0), down(1, 0), left(0, -1), right(0, 1). - Recurse on each neighbour by adding the pair to the current position.
- Write
IsValidCell. It returns whethergrid[row, col] == 1, inside atryblock. Acatchreturnsfalsewhen the index is outside the array, because reading outside an array throws.
The solution in C#
class Solution {
public bool IsValidCell(int[,] grid, int row, int col) {
try {
return grid[row, col] == 1;
} catch (Exception exception) {
return false;
}
}
public void Dfs(int[,] grid, int row, int col) {
if (!IsValidCell(grid, row, col)) {
return;
}
grid[row, col] = 0;
int[][] directions = new int[][] { new int[]{-1, 0}, new int[]{1, 0}, new int[]{0, -1}, new int[]{0, 1} };
foreach (int[] d in directions) {
Dfs(grid, row + d[0], col + d[1]);
}
}
public int NumIslands(int[,] grid) {
int result = 0;
for (int i = 0; i < grid.GetLength(0); ++i) {
for (int j = 0; j < grid.GetLength(1); ++j) {
if (grid[i, j] == 1) {
result++;
Dfs(grid, i, j);
}
}
}
return result;
}
}
The C# details worth knowing:
- Two kinds of 2D array.
int[,]is a rectangular array: one block of memory, always the same number of columns in every row, indexedgrid[i, j].int[][]is a jagged array: an array whose elements are arrays, indexedgrid[i][j]. The grid uses the first kind, while thedirectionslist uses the second, because its elements are small separate arrays. - Bounds are checked. C# never lets you read outside an array. Both
grid[-1, 0]andgrid[0, columns]throw anIndexOutOfRangeException, which is whatIsValidCellrelies on. It also means a column index that is too large doesn't silently read from the next row. - Exceptions are slow. Throwing and catching one costs far more than a comparison, and every land cell on the border throws at least once. Explicit checks do the same job without exceptions:
row >= 0 && row < grid.GetLength(0) && col >= 0 && col < grid.GetLength(1) && grid[row, col] == 1. The lesson's version works for its tests, but the explicit form is the better habit. - The unused
exceptionvariable. The compiler warns that it is never used.catch (IndexOutOfRangeException)without a name would be narrower and cleaner, since it would not hide other kinds of errors.Exception, as used here, also needsusing System;in a standalone file. - The grid is changed in place. Arrays are reference types, so
Dfsmodifies the caller's array. AfterNumIslandsreturns, every cell of the caller's grid is 0. Copy the grid first if you still need the original. - The recursion. Each call of
Dfshandles one cell and calls itself for up to four neighbours. Cells are erased before the recursive calls, which guarantees the recursion ends.
Complexity
Let the grid have R rows and C columns.
Time: O(R * C). The scan looks at each cell once. Each land cell is erased by exactly one Dfs call that gets past the validity check, and every other call returns right away. Every cell is the target of at most four neighbour calls, so the total number of calls is bounded by a constant times the number of cells.
Space: O(R * C) in the worst case. The only extra memory is the call stack. A single snaking island that covers the whole grid makes the recursion go as deep as the number of cells. A very large grid like that can overflow the stack, which ends the program. Solving it with an explicit stack or queue avoids that limit.
Edge cases and common mistakes
- All water. A grid of zeros returns 0, and an empty grid returns 0 too, since both loops run zero times.
- All land.
{{1,1},{1,1}}is one island and returns 1. - Diagonal cells.
{{1,0,1},{0,1,0},{1,0,1}}returns 5, because corners don't connect. - Incrementing inside
Dfs. The count would go up once per cell instead of once per island. - Marking the cell after the recursive calls. The search would revisit cells it is still working on and never finish, until the stack overflows.
- Using
Lengthas a bound. On a 4x5 array,grid.Lengthis 20, not 4 or 5, and the loops would run off the array. - Reusing the grid. Calling
NumIslandstwice on the same array returns 0 the second time, because the first call erased the land.
Testing
{{1,1,1,1,0},{1,1,0,1,0},{1,1,0,0,0},{0,0,0,0,0}}gives1.{{1,1,0,0,0},{1,1,0,0,0},{0,0,1,0,0},{0,0,0,1,1}}gives3.{{1,0,1},{0,1,0},{1,0,1}}gives5.{{0}}gives0.{{1,1},{1,1}}gives1.