Problem overview
The method numIslands receives a grid, [][]int, in which 1 is land and 0 is water. 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 outside edges of the grid count as water.
In the first example, every 1 is linked to the others through up, down, left or right moves, so the answer is 1. In the second, the 2x2 block at the top left, the lone cell in the middle and the pair at the bottom right can't reach each other, so the answer is 3.
Approach
Scan the grid cell by cell. When you meet a land cell, you've found an island, but you can't tell whether you have counted it already: its neighbours are land too, and the scan will reach them next. The fix is to erase the island as soon as you find it. Starting from the land cell, a depth-first search (DFS) visits every land cell connected to it and turns each one into water. When the scan continues, the rest of that island is invisible, and the next 1 it meets belongs to a different island.
So the count goes up exactly once per island, in the scan, and the DFS never touches the count. Each cell is erased at most once and examined a constant number of times, so the whole thing is linear in the size of the grid.
Step by step
The lesson builds numIslands first and writes the helpers it needs afterwards.
- Declare
result := 0. It counts the islands found so far. - Loop over the rows with
ifrom 0 whilei < len(grid). - Loop over the columns with
j, up tolen(grid[0]). Every row has the same length, so the first row tells you how many columns there are. - Test for land:
grid[i][j] == 1. - Count it and call
this.dfs(grid, i, j). This cell was not reached by any earlier search, so it starts a new island.dfsis assumed to exist and to turn the whole island into water. - Return
resultafter the loops. - Write
dfsabovenumIslands, with the same receiver, takinggrid,rowandcoland returning nothing. - Stop at invalid cells: if
this.isValidCell(grid, row, col)is false, return at once. Off-grid cells and water both end the search in that direction. - Mark the cell as water by setting it to 0 before going further. This is what prevents two neighbours from sending the search back and forth forever.
- Declare
directions, a[][2]intholding the four moves up, down, left and right as (row change, column change). - Recurse into each neighbour with
for _, d := range directions, callingdfson(row+d[0], col+d[1]). - Write
isValidCellabovedfs: returnfalsewhen the cell is outside the grid, otherwise return whether it holds a 1. The bounds check comes first, since Go panics when you index out of range.
The solution in Go
type Solution struct{}
func (this Solution) isValidCell(grid [][]int, row int, col int) bool {
if row < 0 || col < 0 || row >= len(grid) || col >= len(grid[0]) {
return false
}
return grid[row][col] == 1
}
func (this Solution) dfs(grid [][]int, row int, col int) {
if !this.isValidCell(grid, row, col) {
return
}
grid[row][col] = 0
directions := [][2]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
for _, d := range directions {
this.dfs(grid, row+d[0], col+d[1])
}
}
func (this Solution) numIslands(grid [][]int) int {
result := 0
for i := 0; i < len(grid); i++ {
for j := 0; j < len(grid[0]); j++ {
if grid[i][j] == 1 {
result++
this.dfs(grid, i, j)
}
}
}
return result
}
The Go details worth a closer look:
- Methods on a struct. Go has no classes.
Solutionis an empty struct, and each function declares a receiver,(this Solution), which places it in the type's method set. The methods call each other through that receiver. The namethisis only a convention borrowed from other languages; Go programmers usually pick a short name based on the type. - The grid is changed in place. A slice is a small header pointing at an underlying array, and passing it to a function copies the header, not the data. So
dfswrites into the caller's grid, and afternumIslandsreturns, every cell of the input is 0. Copy the grid first if you need it afterwards. ||short-circuits. In the bounds check, the conditions are evaluated left to right and stop at the first true one, sogrid[row][col]is never read with a bad index. Note that the check oncoluseslen(grid[0]), which assumes a rectangular grid.- Array elements in a slice.
[][2]intis a slice whose elements are arrays of exactly two integers. In the literal{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}the inner type is omitted because it's already known. - A function with no result just lists no return type, and a bare
returnexits it early.
Complexity
Time: O(m * n) for a grid with m rows and n columns. The scan visits every cell once. Each land cell is turned into water the first time the DFS reaches it and is skipped afterwards, so the searches together do constant work per cell.
Space: O(m * n) in the worst case. The grid is modified in place, so no visited table is needed, but recursion uses stack space. In a grid that is one big island, the recursion can go as deep as the number of land cells. Go grows its goroutine stacks as needed, so ordinary test sizes are fine.
Edge cases and common mistakes
- No land. A grid of zeros returns 0. A grid with no rows also returns 0, because the outer loop never runs and
len(grid[0])is never evaluated. - Diagonal neighbours.
[[1,0,1],[0,1,0],[1,0,1]]has 5 islands, since only the four straight moves connect cells. - Marking after recursing. If the cell is set to 0 after the neighbour calls instead of before, neighbouring cells call each other without end and the program overflows the stack.
- Counting inside
dfs. That would add one per land cell instead of one per island. - Reading before checking. Looking at
grid[row][col]before the bounds check panics for cells on the edge, because neighbours of an edge cell fall outside the grid. - A fully land grid.
[[1,1],[1,1]]gives 1 and leaves the grid all zeros.
Testing
- The first example (a single connected island) gives
1. - The second example gives
3. [[1,0,1],[0,1,0],[1,0,1]]gives5.[[0,0],[0,0]]gives0.[[1,1],[1,1]]gives1.