Max Area of Island
You're given an m x n grid of 0s and 1s, where 1 is land and 0 is water. An island is a group of land cells connected up, down, left, or right; diagonal neighbors don't connect. The area of an island is its number of cells. Return the area of the largest island, or 0 if the grid has no land.
Examples
grid = [[1,1,0,0],[1,0,0,1],[0,0,1,1],[0,0,0,1]] returns 4
The top-left island has 3 cells. The island on the right has 4: (1,3), (2,2), (2,3), and (3,3).
grid = [[0,0],[0,0]] returns 0
There is no land, so there is no island.
grid = [[1]] returns 1
One land cell is an island of area 1.
Constraints
- 1 <= m, n <= 50
- grid[i][j] is 0 or 1.
Hints
This is Number of Islands with one more piece of information per island. What do you need to track during each flood fill?
Use DFS or BFS from each unvisited land cell, counting the cells it reaches.
For each cell with value 1, set it to 0, push it, and pop until the stack is empty, counting each pop and pushing (and zeroing) every land neighbor. Keep the maximum count.
Drill This: Your Approach First
Approach
Scan every cell. When you find land that hasn't been visited, flood fill its island with DFS or BFS, counting cells as you go, and keep the largest count. Mark cells visited by setting them to 0 so no island is counted twice. An explicit stack avoids recursion limits on a large single island. Each cell is pushed and processed a constant number of times: O(m * n) time, O(m * n) space in the worst case.
Time
O(m * n)
Space
O(m * n)
Pitfall
Solutions
class Solution {
public int maxAreaOfIsland(int[][] grid) {
int m = grid.length, n = grid[0].length, best = 0;
int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (grid[r][c] != 1) continue;
int area = 0;
Deque<int[]> stack = new ArrayDeque<>();
grid[r][c] = 0;
stack.push(new int[] {r, c});
while (!stack.isEmpty()) {
int[] cell = stack.pop();
area++;
for (int[] d : dirs) {
int nr = cell[0] + d[0], nc = cell[1] + d[1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 1) {
grid[nr][nc] = 0;
stack.push(new int[] {nr, nc});
}
}
}
best = Math.max(best, area);
}
}
return best;
}
}class Solution:
def maxAreaOfIsland(self, grid) -> int:
m, n = len(grid), len(grid[0])
best = 0
for r in range(m):
for c in range(n):
if grid[r][c] != 1:
continue
area = 0
grid[r][c] = 0
stack = [(r, c)]
while stack:
cr, cc = stack.pop()
area += 1
for nr, nc in ((cr + 1, cc), (cr - 1, cc), (cr, cc + 1), (cr, cc - 1)):
if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:
grid[nr][nc] = 0
stack.append((nr, nc))
best = max(best, area)
return best