Problem overview
The function numIslands receives a grid of 0s and 1s as an Array<IntArray>: a 1 is land and a 0 is water. An island is a group of land cells connected horizontally or vertically. The function returns how many islands the grid has.
In the first example, every 1 is linked to another through side-by-side neighbours, so there is a single island. In the second example, the 2x2 block of ones at the top left is one island, the lone 1 in the third row is another, and the two neighbouring 1s at the bottom right are a third. The answer is 3. The lone 1 touches the block only at a corner, and cells that meet diagonally are not connected.
Approach: count an island, then erase it
Scan the grid cell by cell. The first time the scan meets a land cell, it has found a new island. The difficulty is that an island has many cells, and the scan must not count it again at each of them.
The fix is to erase an island as soon as it is counted. When the scan reaches a 1, add one to the result and run a depth-first search (DFS) from that cell. The search visits every land cell connected to it, directly or through other land cells, and sets each one to 0. When the scan goes on, the rest of that island is already water, so it adds nothing more. Each island is counted exactly once, at the first of its cells that the scan reaches.
The DFS is a recursive function. For one cell it asks whether the cell is land inside the grid. If not, it stops. If so, it turns the cell into water and does the same for the four neighbours: up, down, left and right.
Step by step
The lesson writes the main function first, assuming a helper called dfs exists, and then writes the helpers.
- Declare
resultas avarset to 0. It counts islands, and it changes, so it can't be aval. - Loop over the rows with
i in 0 until grid.size. The range stops beforegrid.size, so it covers exactly the valid row indices. - Loop over the columns with
j in 0 until grid[0].size. Every row has the same length, so the first row's length is the number of columns. - Test whether
grid[i][j] == 1. This cell is land. - Increment
resultinside thatif. This is the only place where the count changes. A land cell reached by the scan 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 it isn't,returnat once. Water and cells off the edge both end the search in that direction. - Mark the cell as water by setting
grid[row][col]to 0 before any recursion. Without this, two neighbouring cells would send the search back and forth forever. - Describe the four moves as pairs of (row change, column change):
(-1, 0)for up,(1, 0)for down,(0, -1)for left and(0, 1)for right. - Recurse on each neighbour by adding the pair to the current position.
- Write
isValidCell. It first returnsfalseif the row or column is negative or too large, and only then reads the cell and returns whether it equals 1. The bounds are checked first because reading outside an array throws.
The solution in Kotlin
class Solution {
fun isValidCell(grid: Array<IntArray>, row: Int, col: Int): Boolean {
if (row < 0 || col < 0 || row >= grid.size || col >= grid[0].size) {
return false
}
return grid[row][col] == 1
}
fun dfs(grid: Array<IntArray>, row: Int, col: Int) {
if (!isValidCell(grid, row, col)) {
return
}
grid[row][col] = 0
val directions = arrayOf(intArrayOf(-1, 0), intArrayOf(1, 0), intArrayOf(0, -1), intArrayOf(0, 1))
for (d in directions) {
dfs(grid, row + d[0], col + d[1])
}
}
fun numIslands(grid: Array<IntArray>): Int {
var result = 0
for (i in 0 until grid.size) {
for (j in 0 until grid[0].size) {
if (grid[i][j] == 1) {
result++
dfs(grid, i, j)
}
}
}
return result
}
}
The Kotlin details worth knowing:
Array<IntArray>. It is an array whose elements areIntArrayrows, indexedgrid[row][col].grid.sizeis the number of rows, andgrid[0].sizeis the length of the first row.- Short-circuit conditions. In
isValidCell, the||operators stop at the first true test. Therow >= grid.sizetest comes before anything readsgrid[0], and the full condition is checked beforegrid[row][col]is read, so no index is ever out of range. - The grid is changed in place. An array is an object, and
dfsreceives a reference to the caller's array, not a copy. AfternumIslandsreturns, every cell of the caller's grid is 0. Copy the grid first if you still need the original. - Parameters are read-only, but the contents of an array are not.
grid[row][col] = 0is allowed even thoughgriditself can't be reassigned. val directions. The variable can't be reassigned, but it points to an array of four small arrays. Eachdin the loop is oneIntArraywith the row change at index 0 and the column change at index 1.for (d in directions)loops over the elements directly, so there is no index to get wrong.
Complexity
Let the grid have R rows and C columns.
Time: O(R * C). The scan looks at each cell once. A land cell is erased by exactly one dfs call that passes the validity check, and every other call returns right away. Each cell is the target of at most four neighbour calls, so the total number of calls is at most a constant times the number of cells.
Space: O(R * C) in the worst case. The extra memory is the call stack. One snaking island that covers the whole grid makes the recursion as deep as the number of cells. On the JVM, a large grid that is entirely land (a few hundred rows and columns is enough) ends the program with a StackOverflowError. For inputs like that, use an explicit stack or a queue instead of recursion.
Edge cases and common mistakes
- All water. A grid with a single cell holding 0 returns 0.
- No rows.
arrayOf(), with no rows at all, returns 0, because the outer loop doesn't run andgrid[0]is never evaluated. - All land. A 2x2 grid of ones is one island, and
numIslandsreturns 1. - Diagonal cells. A 3x3 grid with ones at the four corners and the centre returns 5, because diagonal neighbours aren't connected.
- 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 recurse until the stack overflows.
- Checking bounds after reading. Reading
grid[row][col]first throws anArrayIndexOutOfBoundsExceptionas soon as the search steps off the grid. - Reusing the grid. Calling
numIslandstwice on the same array returns 0 the second time, because the first call erased all the land.
Testing
- Rows
11110,11010,11000,00000give1. - Rows
11000,11000,00100,00011give3. - Rows
101,010,101give5. - The single row
0gives0. - Rows
11,11give1.