GitHub

Max Area of Island medium

Description

Given an m × n binary grid where 1 is land and 0 is water, return the maximum area of an island. An island is a maximal group of 1s connected horizontally or vertically. The area is the count of cells in the island. If there are no islands, return 0.

Examples

> Case 1:
    Input:
        [[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      # the L-shape in the lower-right area is 6 cells
 
> Case 2:
    Input:  [[0,0,0,0,0,0,0,0]]
    Output: 0

Constraints

1 <= m, n <= 50
grid[i][j] is 0 or 1.

Intuition

Almost identical to Number of Islands, with one twist: instead of incrementing a count, we compute the area of each island and track the maximum.

The trick: have the DFS function return the area of the island that includes the current cell. Adding 1 (for the current cell) plus the recursive results from each direction gives the total.

Code

Notice how the DFS function returns a value here — the area — instead of mutating an external counter. That’s the cleaner functional style. It’s the same trick we used on the Day 6 tree problems: each subtree returns a value, the caller combines them.

Why this pattern is so common

“Walk the structure and aggregate” is half of all DFS problems. Examples:

Max Area of Island — aggregate by sum
Diameter of Binary Tree — aggregate by max(left + right + 1)
Path Sum — aggregate by sum along a root-to-leaf path
Count Subtrees with All Same Value — aggregate by “is this subtree uniform?”
Sum of Distances in Tree — aggregate by rerooting

The shape of the aggregation changes; the DFS shape doesn’t.

Analysis

Time: O(m · n) — every cell visited at most once.
Space: O(m · n) worst case for the recursion stack (one giant island).

Number of Islands Clone Graph