Appearance
4.20.3 — Max Area of Island
LeetCode 695 · Medium
The problem
Return the number of cells in the largest island. Return 0 if there is no land.
0 0 1 0 0
0 0 0 0 0
0 1 1 0 1 → 4 (the three-cell island plus... no —
0 1 0 0 1 the largest here is the pair on the right joined
with the one below it: count them per island)In plain English, given a 2D binary grid, an island is a group of 1s connected 4-directionally (horizontal or vertical). The area of an island is the number of cells it contains. You need to return the maximum area of any island in the grid. If the grid contains only 0s, return 0. Grid dimensions typically range up to 50x50.
The pattern
4.20.1 Number of Islands with one change: the flood fill returns how many cells it visited, instead of returning nothing.
Each cell contributes 1, plus whatever the four recursive calls contribute. Water and already-visited cells contribute 0.
That is the whole difference, and it is worth noticing how small it is — the flood fill is a template, and problems differ only in what they accumulate while flooding.
The ELI5 Analogy
Think of the bucket-of-paint analogy from Number of Islands. You are still dumping red paint on unvisited land. But this time, you have an assistant with a tally counter. Every time the paint spreads to a new square of land, the assistant clicks the counter. When the paint stops spreading, the assistant tells you the final tally for that island. You write it down. Then you move on, looking for the next unpainted island. At the end of the day, you look at your notepad and circle the biggest number you wrote down.
What about a Brute Force Approach?
A brute force method might be to start a BFS/DFS from every single 1 in the grid and count the reachable 1s without mutating the grid (re-creating a visited set every time). If the entire grid is one massive island of size N, starting a full search from every single cell would take O(N) work per cell, leading to O(N^2) time complexity. By mutating the grid as we go, we ensure each cell is part of only one search, keeping it firmly at O(N).
The solution
python
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
rows, cols = len(grid), len(grid[0])
def area(r: int, c: int) -> int:
if r < 0 or r >= rows or c < 0 or c >= cols:
return 0
if grid[r][c] != 1:
return 0 # water, or already counted
grid[r][c] = 0 # mark before recursing
return (1
+ area(r + 1, c)
+ area(r - 1, c)
+ area(r, c + 1)
+ area(r, c - 1))
best = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == 1:
best = max(best, area(r, c))
return bestts
function maxAreaOfIsland(grid: number[][]): number {
const rows = grid.length, cols = grid[0].length;
function area(r: number, c: number): number {
if (r < 0 || r >= rows || c < 0 || c >= cols) return 0;
if (grid[r][c] !== 1) return 0;
grid[r][c] = 0;
return 1 + area(r + 1, c) + area(r - 1, c)
+ area(r, c + 1) + area(r, c - 1);
}
let best = 0;
for (let r = 0; r < rows; r++)
for (let c = 0; c < cols; c++)
if (grid[r][c] === 1) best = Math.max(best, area(r, c));
return best;
}The 1 + counts this cell; the four calls count the rest of the island.
Marking before recursing is what makes each cell counted exactly once. Marking afterwards would let a cell be reached again through a neighbour and counted twice, and would also loop forever.
best starts at 0, so a grid with no land returns 0 with no special case.
Everything else is identical to 4.20.1.
Code Walkthrough & Trace
Consider a tiny 1D grid [1, 1, 0].
| Step | Action | State | Return Value |
|---|---|---|---|
| 1 | Loop r=0, c=0. Call area(0, 0) | Grid: [1, 1, 0]. best = 0 | |
| 2 | Inside area(0, 0). Mark grid[0][0] = 0 | Grid: [0, 1, 0] | |
| 3 | Calls area(0, 1) | ||
| 4 | Inside area(0, 1). Mark grid[0][1] = 0 | Grid: [0, 0, 0] | |
| 5 | area(0, 1) calls neighbors | All return 0 | Returns 1 + 0 = 1 |
| 6 | Back to area(0, 0) | Returns 1 + 1 = 2 | |
| 7 | Update best | best = max(0, 2) = 2 | |
| 8 | Loop continues... calls area(0, 1) | Returns 0 (it's water now) | |
| 9 | Finish | Returns 2 |
Key lines explained:
return 1 + area(...) + ...- This is where the counting happens. The1represents the current cell, and we sum the area of all adjacent land.
Complexity
O(rows \times cols) time and space. To break it down: Time complexity is O(rows \times cols) because the nested for loops iterate over every cell exactly once, doing O(1) work to check if grid[r][c] == 1. When we do find a 1, the area DFS visits it, mutates it to 0, and never visits it again. Thus, across the entire execution, each cell is processed only a constant number of times. Space complexity is O(rows \times cols) because the recursion call stack could potentially go as deep as the total number of cells if the entire grid is one long snake-like island.
The family, made explicit
The flood fill accumulates something. Which something is the whole problem:
| problem | the flood returns |
|---|---|
| Number of Islands | nothing — you count the calls |
| Max Area of Island | the cell count |
| Count Sub Islands | whether every cell was also land in a second grid |
| Number of Closed Islands | whether the island ever touched the border |
| Number of Distinct Islands | the list of cell offsets, used as a shape fingerprint |
| Island Perimeter | the number of edges facing water or the outside |
Number of Distinct Islands is worth a moment, because it combines two chapters. Two islands are the same if one can slide onto the other, so the fingerprint is the set of cell positions relative to the island's first cell. Record those offsets during the flood, turn them into a tuple, and count the distinct tuples with a set. That is 4.4.4 Group Anagrams's canonical-form move applied to shapes.
What the interviewer will push on
"How is this different from counting islands?" The flood returns a count instead of nothing.
"Why mark before recursing?" Otherwise cells are counted twice and the recursion never ends.
"What if you could not modify the grid?" A separate visited array, same complexity.
"How would you find the largest island you could make by flipping one water cell to land?" That is LeetCode 827, and it is the genuinely interesting follow-up. Flood once, giving each island an id and a size stored in a map. Then for every water cell, look at its four neighbours, collect their distinct island ids, and sum those sizes plus one. The "distinct" is the trap — two neighbours may belong to the same island and must not be double counted. Still O(rows \times cols).
One thing to volunteer: name the family. "This is the flood fill again; the only question in these problems is what you accumulate while flooding." Saying it turns six problems into one.
Next: 4.20.4 Pacific Atlantic Water Flow — where the trick is to run the search backwards.