Max Area of Island
Problem Statement
You are given an m x n binary grid where 1 is land and 0 is water. An island is a 4-directionally connected group of 1s.
Return the area (number of cells) of the largest island. If there is no island, return 0.
Input
A 2D int grid of 0s and 1s.
Output
An integer: the maximum island area (0 if there is none).
Constraints
- •
m == grid.length - •
n == grid[i].length - •
1 <= m, n <= 50 - •
grid[i][j] is 0 or 1
Examples
Example 1
grid = [ [0,0,1,0,0], [0,1,1,1,0], [0,0,1,0,0], [1,1,0,0,0] ]
5Example 2
grid = [[0,0,0],[0,0,0]]
0Learning Objectives
- Have a traversal *return a value* (the component size) instead of just marking cells.
- Aggregate per-component results into a global maximum.
- Reinforce that summing 1 + area(neighbours) counts the connected cells.
Intuition
This is Number of Islands with a twist: instead of counting islands, you measure each one and keep the biggest. The traversal is identical — you still sink each island so it is counted once — but now the DFS returns the number of cells it sank. A land cell contributes 1 for itself plus whatever its four recursive calls report.
Think of it as the DFS bubbling a size back up the call stack: leaves return their single cell, and each parent adds up the sizes of the regions below it. The outer loop simply tracks the largest value any single traversal produced.
Common mistakes
- ×Returning early without adding the current cell, so the count is off by the component's cell count.
- ×Forgetting to reset or compare against the running maximum for every seed.
- ×Not sinking the cell before recursing, which double-counts cells and inflates the area.
Algorithm Explanation
- Keep a running max, initially 0.
- For each unvisited land cell, run a DFS that returns the size of its island.
- The DFS returns 0 for water/out-of-bounds; otherwise it sinks the cell and returns 1 + the sum of the four recursive calls.
- Update max with each island's returned size.
- Return max.
Solutions
Solution: DFS returning component size
Run the standard sink-DFS, but let it return the count of cells it consumed. The largest returned value across all seeds is the answer.
Step-by-step
- area(r, c) returns 0 when the cell is out of bounds or water.
- Otherwise it marks the cell 0 (so it is not recounted) and returns 1 plus the areas of its four neighbours.
- The main loop takes the max over every seed's returned area.
O(m · n)
O(m · n)
Each cell is visited once; recursion depth is bounded by the largest island.
Java implementation
Dry Run
Sample input
Trace area() on the bottom-left island of grid = [[0,0],[1,1]] seeded at (1,0).
| Call | Cell | Returns | Running max |
|---|---|---|---|
| area(1,0) | (1,0) | 1 + area(neighbours) | - |
| area(2,0) | out of bounds | 0 | - |
| area(0,0) | (0,0) = 0 | 0 | - |
| area(1,1) | (1,1) = 1 | 1 + ... | - |
| area(1,1) kids | all 0/oob | 0 each | - |
| area(1,1) | resolves | 1 | - |
| area(1,0) | resolves | 1 + 0 + 0 + 1 + 0 = 2 | 2 |
The seed cell (1,0) counts itself (1) and its only land neighbour (1,1) which returns 1, giving an island area of 2. The running max becomes 2.
Interview Tips
The delta from Number of Islands is tiny — say so explicitly and show that you understand the traversal by having it return a value. Interviewers use this to check whether you can adapt a known template rather than memorise a single answer. A common follow-up asks for the count of distinct island shapes, which needs canonical shape hashing — mention it if you have time.
Likely follow-ups
- Return the number of islands whose area is at least k.
- Count distinct island shapes (normalise each island's relative coordinates).
- Solve it with BFS or with Union-Find and compare.
Similar Problems
Key Takeaways
- A traversal can return an aggregate (size, sum, depth), not just mark visited.
- Component size = 1 + the sizes returned by the recursive neighbour calls.
- Track a global maximum across all component seeds.