Number of Islands
MediumThe problem
grid is a map where "1" is land and "0" is water. An island is a group of land cells connected up, down, left or right (not diagonally). Return how many islands there are.
- Example 1Input: grid = [["1", "1", "0"], ["0", "1", "0"], ["0", "0", "1"]]Output: 2
The three connected land cells in the top-left form one island, and the bottom-right cell is another.
- Example 2Input: grid = [["1", "1", "1"], ["0", "1", "0"], ["1", "1", "1"]]Output: 1
All the land is joined through the middle column.
- 1 ≤ rows, columns ≤ 300
- Each cell is the byte "1" or "0"
Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.
Try it here
Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.
Hints, one at a time
Nudge
Each island is one connected blob of land. How do you make sure you count a blob only once?
The idea
Scan the grid; on unseen land increment the count and flood-fill (DFS/BFS) the whole island, marking cells visited.
Target: O(m·n) time
Go function shape
func numIslands(grid [][]byte) intReference solution
Tested with go test. Try it yourself first, then compare.
// NumIslands: every cell is a node, its 4 neighbours are the edges.
// Each unvisited land cell starts a new island; DFS sinks the whole island.
func NumIslands(grid [][]byte) int {
count := 0
var sink func(r, c int)
sink = func(r, c int) {
if r < 0 || c < 0 || r >= len(grid) || c >= len(grid[r]) || grid[r][c] != '1' {
return
}
grid[r][c] = '0' // mark visited by overwriting (the grid is our visited set)
sink(r+1, c)
sink(r-1, c)
sink(r, c+1)
sink(r, c-1)
}
for r := range grid {
for c := range grid[r] {
if grid[r][c] == '1' {
count++
sink(r, c)
}
}
}
return count
}