695. Max Area of Island #

Problem #

Given a non-empty 2D array grid of 0’s and 1’s, an island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)

Example 1:

[[0,0,1,0,0,0,0,1,0,0,0,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,1,1,0,1,0,0,0,0,0,0,0,0],
 [0,1,0,0,1,1,0,0,1,0,1,0,0],
 [0,1,0,0,1,1,0,0,1,1,1,0,0],
 [0,0,0,0,0,0,0,0,0,0,1,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,0,0,0,0,0,0,1,1,0,0,0,0]]

Given the above grid, return6. Note the answer is not 11, because the island must be connected 4-directionally.

Example 2:

[[0,0,0,0,0,0,0,0]]

Given the above grid, return0.

Note: The length of each dimension in the given grid does not exceed 50.

Problem Summary #

Given a non-empty 2D array grid containing some 0s and 1s. An island is a combination of adjacent 1s (representing land), where “adjacent” requires that two 1s must be adjacent horizontally or vertically. You may assume that the four edges of grid are surrounded by 0s (representing water). Find the maximum area of an island in the given 2D array. (If there is no island, return an area of 0.)

Solution Approach #

• Given a map, calculate the area of the islands on it. Note that the definition of an island is that it is surrounded by sea (points with value 0); if land (points with value 1) is adjacent to the edge of the map, it cannot be counted as an island.
• This problem has the same solution approach as Problem 200 and Problem 1254: DFS deep search. However, this problem requires handling 2 additional things: one is to note that islands adjacent to the edge cannot be counted, and the other is to dynamically maintain the maximum area of an island.

Code #

var dir = [][]int{
	{-1, 0},
	{0, 1},
	{1, 0},
	{0, -1},
}

func maxAreaOfIsland(grid [][]int) int {
	res := 0
	for i, row := range grid {
		for j, col := range row {
			if col == 0 {
				continue
			}
			area := areaOfIsland(grid, i, j)
			if area > res {
				res = area
			}
		}
	}
	return res
}

func isInGrid(grid [][]int, x, y int) bool {
	return x >= 0 && x < len(grid) && y >= 0 && y < len(grid[0])
}

func areaOfIsland(grid [][]int, x, y int) int {
	if !isInGrid(grid, x, y) || grid[x][y] == 0 {
		return 0
	}
	grid[x][y] = 0
	total := 1
	for i := 0; i < 4; i++ {
		nx := x + dir[i][0]
		ny := y + dir[i][1]
		total += areaOfIsland(grid, nx, ny)
	}
	return total
}