Max Area of Island
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). Its area is the number of cells in it. Return the largest island area, or 0 if there is no land.
- Example 1Input: grid = [[0, 1, 1], [0, 1, 0], [1, 0, 0]]Output: 3
The three connected cells in the top right form the biggest island. The bottom-left cell is an island of area 1.
- Example 2Input: grid = [[0, 0, 0]]Output: 0
There is no land.
- 1 ≤ rows, columns ≤ 300
- Each cell is 0 or 1
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
The same flood fill, but now it should report how big the blob was.
The idea
DFS returns 1 + the sizes of its four neighbours; track the maximum over all starting cells.
Target: O(m·n) time
Go function shape
func maxAreaOfIsland(grid [][]int) intReference solution
Tested with go test. Try it yourself first, then compare.
// MaxAreaOfIsland: flood-fill each island and report its size. Sinking a visited cell (setting it to 0)
// doubles as the "visited" mark.
func MaxAreaOfIsland(grid [][]int) int {
var area func(r, c int) int
area = func(r, c int) int {
if r < 0 || c < 0 || r >= len(grid) || c >= len(grid[0]) || grid[r][c] == 0 {
return 0
}
grid[r][c] = 0
return 1 + area(r+1, c) + area(r-1, c) + area(r, c+1) + area(r, c-1)
}
best := 0
for r := range grid {
for c := range grid[r] {
best = max(best, area(r, c))
}
}
return best
}