Problem

You are given an m x n binary matrix grid. 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.

The area of an island is the number of cells with a value 1 in the island.

Return the maximum area of an island in grid. If there is no island, return 0.

Examples

Example 1:

$$ \begin{bmatrix} \colorbox{blue}{0} & \colorbox{blue}{0} & \colorbox{orange}{1} & \colorbox{blue}{0} & \colorbox{blue}{0} & \colorbox{blue}{0} & \colorbox{blue}{0} & \colorbox{orange}{1} & \colorbox{blue}{0} & \colorbox{blue}{0} & \colorbox{blue}{0} & \colorbox{blue}{0} & \colorbox{blue}{0} \\ \colorbox{blue}{0} & \colorbox{blue}{0} & \colorbox{blue}{0} & \colorbox{blue}{0} & \colorbox{blue}{0} & \colorbox{blue}{0} & \colorbox{blue}{0} & \colorbox{orange}{1} & \colorbox{orange}{1} & \colorbox{orange}{1} & \colorbox{blue}{0} & \colorbox{blue}{0} & \colorbox{blue}{0} \\ \colorbox{blue}{0} & \colorbox{orange}{1} & \colorbox{orange}{1} & \colorbox{blue}{0} & \colorbox{orange}{1} & \colorbox{blue}{0} & \colorbox{blue}{0} & \colorbox{blue}{0} & \colorbox{blue}{0} & \colorbox{blue}{0} & \colorbox{blue}{0} & \colorbox{blue}{0} & \colorbox{blue}{0} \\ \colorbox{blue}{0} & \colorbox{orange}{1} & \colorbox{blue}{0} & \colorbox{blue}{0} & \colorbox{orange}{1} & \colorbox{orange}{1} & \colorbox{blue}{0} & \colorbox{blue}{0} & \colorbox{orange}{1} & \colorbox{blue}{0} & \colorbox{orange}{1} & \colorbox{blue}{0} & \colorbox{blue}{0} \\ \colorbox{blue}{0} & \colorbox{orange}{1} & \colorbox{blue}{0} & \colorbox{blue}{0} & \colorbox{orange}{1} & \colorbox{orange}{1} & \colorbox{blue}{0} & \colorbox{blue}{0} & \colorbox{orange}{1} & \colorbox{orange}{1} & \colorbox{orange}{1} & \colorbox{blue}{0} & \colorbox{blue}{0} \\ \colorbox{blue}{0} & \colorbox{blue}{0} & \colorbox{blue}{0} & \colorbox{blue}{0} & \colorbox{blue}{0} & \colorbox{blue}{0} & \colorbox{blue}{0} & \colorbox{blue}{0} & \colorbox{blue}{0} & \colorbox{blue}{0} & \colorbox{orange}{1} & \colorbox{blue}{0} & \colorbox{blue}{0} \\ \colorbox{blue}{0} & \colorbox{blue}{0} & \colorbox{blue}{0} & \colorbox{blue}{0} & \colorbox{blue}{0} & \colorbox{blue}{0} & \colorbox{blue}{0} & \colorbox{orange}{1} & \colorbox{orange}{1} & \colorbox{orange}{1} & \colorbox{blue}{0} & \colorbox{blue}{0} & \colorbox{blue}{0} \\ \colorbox{blue}{0} & \colorbox{blue}{0} & \colorbox{blue}{0} & \colorbox{blue}{0} & \colorbox{blue}{0} & \colorbox{blue}{0} & \colorbox{blue}{0} & \colorbox{orange}{1} & \colorbox{orange}{1} & \colorbox{blue}{0} & \colorbox{blue}{0} & \colorbox{blue}{0} & \colorbox{blue}{0} \end{bmatrix} $$

1
2
3
4
5

Input:
grid =[[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]]
Output:
 6
Explanation: The answer is not 11, because the island must be connected 4-directionally.

Example 2:

1
2
3
4

Input:
grid =[[0,0,0,0,0,0,0,0]]
Output:
 0

Solution

Note that, it is more like perimeter than area.

Method 1 - DFS with Array Modification

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

public int maxAreaOfIsland(int[][] grid) {
	int m = grid.length;
	int n = grid[0].length;

	int max = 0;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			max = Math.max(max, dfs(grid, i, j));
		}
	}

	return max;
}

private int dfs(int[][] grid, int i, int j) {
	if (i < 0 || i >= grid.length || j < 0 || j >= grid[i].length || grid[i][j] != 1) {
		return 0;
	}

	grid[i][j] = 0; // sink this part of island
	int count = 1;
	count += dfs(grid, i + 1, j);
	count += dfs(grid, i - 1, j);
	count += dfs(grid, i, j + 1);
	count += dfs(grid, i, j - 1);
	return count;
}

Complexity

  • ⏰ Time complexity: O(m*n)
  • 🧺 Space complexity: O(min(m, n)) assuming recursion stack in the dfs() function. %%

Method 2 - DFS with Visited Set

%%