Max Area of Island — Solution

Problem

You have a 2D grid of 0s (water) and 1s (land). An island is a group of 1s connected horizontally or vertically — diagonal connections don't count. Return the area (number of 1s) of the largest island. If the grid is all water, return 0.

• Input: the grid above
• Output: 3
• Explanation: the island in the top-left has area 3; the island in the bottom-right also has area 3; both tie for largest

A counter-example: a grid of all 0s returns 0 because there are no islands at all.

Intuition

Every land cell belongs to exactly one island, so the problem reduces to: find every island (connected component of 1s), measure its size, and return the biggest. The key insight is that during a depth-first search we can mark each visited cell as 0 — this prevents revisiting and eliminates the need for a separate visited structure.

Solution — DFS with In-Place Marking

Start a DFS from every unvisited land cell. The DFS marks each cell it visits as 0 (water) and returns 1 plus the area contributed by each neighbor. After the DFS returns, we have the full area of that island. We track the running maximum.

1. Iterate over every cell in the grid.
2. Skip cells that are 0 (water or already visited).
3. For each unvisited land cell, launch a DFS that returns the island's total area.
4. In the DFS, immediately mark the current cell as 0 so it won't be counted again.
5. Recursively explore all four neighbors, summing their returned areas.
6. After the DFS returns, update the running maximum and continue.

1def maxAreaOfIsland(grid: list[list[int]]) -> int:
2    rows, cols = len(grid), len(grid[0])
3
4    def dfs(row, col):
5        # out of bounds or water — contributes 0 area
6        if row < 0 or row >= rows or col < 0 or col >= cols or grid[row][col] == 0:
7            return 0
8        grid[row][col] = 0  # mark visited so we don't count this cell again
9        return 1 + dfs(row + 1, col) + dfs(row - 1, col) + dfs(row, col + 1) + dfs(row, col - 1)
10
11    max_area = 0
12    for row in range(rows):
13        for col in range(cols):
14            if grid[row][col] == 1:
15                max_area = max(max_area, dfs(row, col))
16    return max_area

Time: O(m × n) — each cell is visited at most once across all DFS calls.

Space: O(m × n) — the call stack can grow as deep as the number of land cells in the worst case (a fully connected island that fills the grid).

Complexity Summary

Common Mistakes

• Forgetting to mark cells before recursing — without grid[row][col] = 0 before the recursive calls, each neighbor re-enters the current cell and area counts blow up (or the recursion loops infinitely).
• Checking bounds after indexing — accessing grid[row][col] before the bounds check causes an index-out-of-bounds error; the bounds check must come first in the if condition.
• Using 8-directional neighbors — the problem specifies only horizontal and vertical connections; including diagonals merges islands that shouldn't be merged.
• Not resetting the grid for multiple test calls — if the same grid object is reused across test cases, the in-place marking from the first call corrupts subsequent calls; use a separate visited set when input mutation isn't acceptable.
• Returning max_area from inside the DFS — the DFS should return the local area contribution (1 + neighbors), not the global max; the maximum tracking belongs in the outer loop.

Related Problems

• Number of Islands — same DFS/BFS pattern but count distinct components instead of measuring their size
• Flood Fill — DFS to repaint a connected region, identical traversal structure
• 01 Matrix — multi-source BFS from all 0-cells outward, the grid-traversal complement to island problems
• Rotting Oranges — multi-source BFS to spread state across connected cells each round
• Surrounded Regions — DFS to identify connected components that touch the border versus those that don't