Problem overview
The method sizeOfIslands receives a grid of 0s and 1s as a [][]int. A 1 is land and a 0 is water. An island is a group of land cells connected horizontally or vertically, and diagonal contact doesn't connect cells. The method returns a slice with the size, in cells, of every island. The sizes can come in any order.
In the first example, all the 1s link up into one island of 9 cells, so the answer is [9]. In the second, the 1s in the top-left 2x2 block form an island of 4, the lone 1 below them is an island of 1, and the two 1s at the bottom right are an island of 2. The cell with the single 1 touches the block only at a corner, so it is separate. This solution returns the sizes in scanning order, [4 1 2].
Approach: find an island, then measure and erase it
Scan the grid cell by cell. When the scan meets a land cell, it has found an island that hasn't been measured yet. Then a depth-first search (DFS) starts from that cell, visits every land cell connected to it, and counts them. The search also turns each visited cell into water. That erasing does two jobs: it stops the search from walking back and forth between two neighbors forever, and it hides the island from the rest of the scan, so the island is measured only once.
The DFS asks the same question for each cell: is this cell land inside the grid? If not, stop. If so, count it, turn it into water, and ask the same question for the four neighbors (up, down, left and right). Off-grid and water neighbors need no special handling. The first check rejects them.
Step by step
- Declare
noOfCellswithvarat package level, outside any function. All the recursive calls ofdfsadd to this one counter. - In
sizeOfIslands, declareresultas an empty[]int. Island sizes are appended to it. - Loop over the rows with
iup tolen(grid), and over the columns withjup tolen(grid[0]). Together they visit every cell. - Check
grid[i][j] == 1. A land cell reached here was not erased by an earlier search, so it belongs to a new island. - Reset
noOfCellsto 0 before exploring, so it counts only this island. - Call
dfs(grid, i, j)through the receiver, then appendnoOfCellstoresultand assign the result ofappendback. - Return
resultafter both loops. - Write
dfsas a method with the parametersgrid,rowandcoland no return value. First askisValidCell, and return immediately if the cell is not valid. - Count and erase: increment
noOfCellsand setgrid[row][col]to 0. - Describe the four moves as
directions, a[][2]intof (row change, column change) pairs, and calldfson each neighbor(row+d[0], col+d[1]). - Write
isValidCell. It is one condition joined with&&: the row is in range, the column is in range, and the cell holds a 1.
The solution in Go
type Solution struct{}
func (this Solution) isValidCell(grid [][]int, row int, col int) bool {
return row >= 0 && row < len(grid) &&
col >= 0 && col < len(grid[0]) &&
grid[row][col] == 1
}
func (this Solution) dfs(grid [][]int, row int, col int) {
if !this.isValidCell(grid, row, col) {
return
}
noOfCells++
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])
}
}
var noOfCells int
func (this Solution) sizeOfIslands(grid [][]int) []int {
result := []int{}
for i := 0; i < len(grid); i++ {
for j := 0; j < len(grid[0]); j++ {
if grid[i][j] == 1 {
noOfCells = 0
this.dfs(grid, i, j)
result = append(result, noOfCells)
}
}
}
return result
}
The Go details worth knowing:
- There is no class and no
thiskeyword.Solutionis an empty struct, and(this Solution)is a receiver, an ordinary parameter that happens to be namedthis. Inside the methods it is used to call the other methods, as inthis.dfs(...). - The counter is a package-level variable, not a field. The methods have a value receiver of an empty struct, so there is nowhere on
Solutionto keep the count, and each recursive call updates the same variable. It needs a reset before each island. - The grid is modified in place. A
[][]intshares its rows with the caller, so settinggrid[row][col] = 0insidedfschanges the caller's grid. After the first example is processed, the whole grid is zeros. Copy the grid first if the original is still needed. - Short-circuit
&&makesisValidCellsafe. When the row or column is out of range, the comparison fails beforegrid[row][col]is read, so there's no index-out-of-range panic. A line ending with&&continues on the next line. result := []int{}starts as an empty, non-nil slice, so a grid with no land returns[].[][2]int{{-1, 0}, ...}is a slice of fixed-size arrays, a compact way to hold row and column offsets. In therangeloop,dis a copy of each pair.
Complexity
Each cell is looked at by the scan once. Each land cell is also entered by the DFS once, because it is erased on entry, and each such visit tries four neighbors. For a grid with R rows and C columns the time is O(R * C). Extra space is the recursion stack, which can reach the size of the largest island, O(R * C) in the worst case such as one snake-shaped island.
Edge cases and common mistakes
- No land. A grid of zeros gives
[]. - A single cell.
[[1]]gives[1]. - Diagonal contact. In a checkerboard such as
[[1,0,1],[0,1,0],[1,0,1]]the five 1s touch only at corners, so the answer is five islands of size 1. - Forgetting the reset. Without
noOfCells = 0each island's size would include all the earlier islands. - Not erasing the cell. If
grid[row][col]stays 1, two neighbors send the search back and forth until the stack overflows, and a surviving island would be counted again by the scan. - Counting in the wrong place. Count after the validity check. Counting before it adds every water and off-grid neighbor.
- Appending without assigning.
append(result, noOfCells)alone discards the grown slice.
Testing
[[1,1,0,0,0],[1,1,0,0,0],[0,0,1,0,0],[0,0,0,1,1]]returns[4 1 2].[[1,1,1],[1,1,1]]returns[6].[[1,0,1,1],[0,0,0,1],[1,1,0,0]]returns[1 3 2].[[0,0],[0,0]]returns[].