Graphs · LC #695
Max Area of Island
Find the largest island area in a binary integer grid by DFS flood-fill that returns cell count instead of just marking visited.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
You are given an `m x n` binary matrix `grid`. An island is a group of `1`s (representing land) connected 4-directionally. Return the maximum area of an island in the grid. If there is no island, return `0`.
Sample I/O
Input: [[0,0,1,0,0],[0,1,1,1,0],[0,1,0,1,1]] Output: 6 Input: [[0,0,0]] Output: 0
Time: O(m×n) · Space: O(m×n)
Intuition
How to Think About It
Intuition
Same flood-fill as Number of Islands, but DFS returns the count of cells consumed rather than just marking them. Each recursive call returns 1 + sum of all four directional calls, naturally accumulating island size as the stack unwinds.
Core Concept
DFS returning area. Base case: out-of-bounds or cell is 0 → return 0. Otherwise: mark cell as 0 (visited), return 1 + dfs(up) + dfs(down) + dfs(left) + dfs(right). Track global max of all returned values.
When to use
When Number-of-Islands-style traversal needs to accumulate a per-component metric (area, sum, count of special cells). Any grid problem where you need a property of each connected component.
When NOT to use
When only the count of components matters (simpler to not return values). When the grid must not be mutated - use a separate visited array.
Key Insights
What to Know Cold
- DFS returning count is an elegant pattern: no separate accumulator needed, the call stack naturally sums.
- Marking cells as 0 before recursing prevents double-counting and infinite recursion.
- Return 0 for out-of-bounds or water cells - these contribute nothing to area.
- The maximum is tracked outside the DFS; DFS only computes per-island area.
- Union-Find alternative: union adjacent land cells, track component sizes in a size array.
1 example
Worked Examples
DFS area-returning flood fill
3×5 grid with a 6-cell island.
For each unvisited land cell, run area-DFS; update global max.
function maxAreaOfIsland(grid: number[][]): number {
function dfs(i: number, j: number): number {
if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] !== 1) return 0;
grid[i][j] = 0;
return 1 + dfs(i+1, j) + dfs(i-1, j) + dfs(i, j+1) + dfs(i, j-1);
}
let max = 0;
for (let i = 0; i < grid.length; i++)
for (let j = 0; j < grid[0].length; j++)
max = Math.max(max, dfs(i, j));
return max;
}Output: 6
Natural follow-up to Number of Islands. Interviewers check whether you can modify the DFS return type cleanly vs. using a global accumulator.