Max Area of Island: Grid DFS Flood Fill, Step by Step
Solve Max Area of Island with a grid DFS flood fill — sink each island as you count it, track the running maximum. Intuition, JavaScript code, and complexity.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Max Area of Island is the problem that turns a grid into a graph in your head. Once you see that a matrix of 1s and 0s is really a graph — each land cell a node, each shared edge between neighbors a connection — a whole family of problems collapses into one technique: flood fill. Walk into any land cell, spread out to everything connected to it, and count what you touched.
The twist that trips people up is bookkeeping. You need to visit every cell, but never count the same island twice, and never count a single cell twice. The elegant trick is to sink land as you visit it — flip each 1 to 0 the moment you step on it — so the grid itself becomes your visited set.
Master this and you've got the core loop behind Number of Islands, flood-fill paint tools, and connected-component counting on any grid.
The problem
You're given an m x n binary matrix grid. A 1 is land, a 0 is water. An island is a group of 1s connected 4-directionally — up, down, left, right, but not diagonally. The area of an island is the number of land cells in it. Return the area of the largest island, or 0 if there is none.
Input:
[0, 0, 1, 0, 0]
[0, 1, 1, 1, 0]
[0, 0, 0, 0, 0]
[0, 1, 1, 0, 0]
Output: 4The top island is a plus/T shape spanning (0,2), (1,1), (1,2), (1,3) — area 4. The bottom island is (3,1), (3,2) — area 2. The answer is the larger of the two: 4.
Two details shape the solution: connectivity is 4-directional only (diagonal touches don't merge islands), and you want the maximum area, so you must measure every island and keep the running best.
The brute force baseline
You can't skip touching cells — every land cell must be examined at least once to know which island it belongs to. So there's no naive nested-pair blow-up here the way there is in an array problem. The real trap is a different kind of slowness: re-counting.
If you scan the grid, and for every land cell you launch a fresh search over the whole island it sits in, you re-measure the same island once per cell it contains. A single island of area k gets fully traversed k times — turning honest O(m·n) work into O(m·n·k). On a solid field of land that's roughly O((m·n)²).
// Slow: measures the same island once per cell it contains
function maxAreaSlow(grid) {
let max = 0;
for (let r = 0; r < grid.length; r++) {
for (let c = 0; c < grid[0].length; c++) {
if (grid[r][c] === 1) {
// re-explores the ENTIRE island from scratch, every time
max = Math.max(max, measureIsland(grid, r, c, new Set()));
}
}
}
return max;
}The fix isn't a smarter data structure — it's making sure each cell is counted exactly once.
The key insight: sink as you go
The pattern is grid DFS flood fill, and the insight is to destroy land as you count it.
When your scan finds a 1, that's the start of an island nobody has counted yet. Launch a depth-first search from that cell. The DFS does two things at each cell it enters: it flips the cell to 0 (sinks it), then recurses into all four neighbors, summing the areas they report back.
Sinking is the whole game. Because a visited cell is now water, no later scan will restart an island on it, and no recursive branch will loop back onto it. The grid is the visited set — no separate Set or boolean[][] needed. Every land cell is entered exactly once across the entire run, which is what gets you back to linear time.
Each DFS returns the total area it flooded. The outer scan compares that against a running maxArea and moves on. Since sinking guarantees the next 1 the scan finds belongs to an entirely different island, you measure each island exactly once.
The optimal solution
This mirrors the CODE_LINES from the interactive visualizer — an inner recursive dfs that returns an area, driven by a full grid scan.
function maxAreaOfIsland(grid) {
let maxArea = 0;
const rows = grid.length;
const cols = grid[0].length;
// DFS: explore one island, sink it, return its size
function dfs(r, c) {
// Out of bounds, or water / already-visited land
if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] === 0) {
return 0;
}
grid[r][c] = 0; // sink this cell so it's never revisited
let area = 1; // this cell counts as 1
area += dfs(r + 1, c); // down
area += dfs(r - 1, c); // up
area += dfs(r, c + 1); // right
area += dfs(r, c - 1); // left
return area;
}
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (grid[r][c] === 1) {
maxArea = Math.max(maxArea, dfs(r, c));
}
}
}
return maxArea;
}The base case does triple duty: it catches out-of-bounds coordinates, real water, and land you've already sunk — all with the single check grid[r][c] === 0. Sinking before recursing is what stops the four-way branch from bouncing back onto the cell you just entered.
Walkthrough
Trace this 3×3 grid, where the scan order is row by row, left to right:
1 1 0
0 1 0
0 0 1The scan hits (0,0) first and launches dfs(0,0). Here's how that first flood fill unfolds — the DFS explores down, up, right, left, and sinks each cell it accepts:
| DFS call | Grid at that cell | Accepted? | area returned |
|---|---|---|---|
| dfs(0,0) | 1 | sink → 0, recurse | 3 (built below) |
| dfs(1,0) down | 0 | water → base case | 0 |
| dfs(-1,0) up | out of bounds | reject | 0 |
| dfs(0,1) right | 1 | sink → 0, recurse | 2 |
| — dfs(1,1) down | 1 | sink → 0, recurse | 1 |
| — — all 4 neighbors | water / oob / sunk | reject | 0 each |
| — dfs(0,2), dfs(0,0) etc | 0 (sunk/water) | reject | 0 |
| dfs(0,-1) left | out of bounds | reject | 0 |
dfs(1,1) sinks itself and finds no live neighbors, returning 1. dfs(0,1) collects that: 1 + 1 = 2. dfs(0,0) collects everything: 1 + 0 (down) + 0 (up) + 2 (right) + 0 (left) = 3. So the first island has area 3, and maxArea becomes 3.
The scan continues, but every cell it now sees in the top island reads 0 — already sunk. It skips through until (2,2), still a 1, and launches dfs(2,2). That cell has no land neighbors, so it returns area 1. Since 1 < 3, maxArea stays 3.
| Scan reaches | grid value | Action | maxArea |
|---|---|---|---|
| (0,0) | 1 | dfs → area 3 | 3 |
| (0,1)…(2,1) | 0 (sunk or water) | skip | 3 |
| (2,2) | 1 | dfs → area 1 | 3 |
Final answer: 3.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Re-count per cell | O((m·n)²) | O(m·n) | each island re-explored once per cell in it |
| DFS flood fill (sink) | O(m·n) | O(m·n) | every cell visited once; recursion depth up to all cells |
Time is O(m · n): the outer scan touches each cell once, and because sinking guarantees no cell is entered by DFS more than once, the total recursive work across all islands is also bounded by the cell count. Space is O(m · n) in the worst case — a grid that is entirely land forms a single snake-shaped recursion whose call stack can hold every cell at once. Sinking the grid means no extra visited structure, so the stack is the only real memory cost.
Common mistakes
- Counting diagonals. The problem is 4-directional. Adding
(r±1, c±1)recursion merges islands that only touch at a corner and inflates the answer. - Forgetting to sink before recursing. If you recurse first and mark later,
dfs(r+1,c)can call back into(r,c)before it's sunk — infinite recursion or a stack overflow. - Using a separate visited set but never checking it. If you keep a
visitedstructure yet forget thegrid[r][c] === 0early return, you'll still re-enter cells. Pick one mechanism (sink or a visited set) and let the base case honor it. - Returning the island count instead of the area. This is Number of Islands' answer, not this one. Here
dfsmust return and sum areas, not just tally how many times you launched it. - Mutating a grid the caller still needs. Sinking destroys the input. If the caller reuses
gridafterward, clone it first or use a visited set instead.
Where this pattern shows up next
Grid and graph DFS is one of the most transferable interview patterns. Once flood fill clicks, these build directly on it:
- Redundant Connection — connected-component thinking on an explicit edge list, where union-find or DFS detects the cycle-closing edge.
- Course Schedule II — DFS on a directed graph for topological ordering and cycle detection.
- Shortest Path in Binary Matrix — the same grid, but BFS for shortest distance instead of DFS for area.
- Network Delay Time — weighted-graph traversal where Dijkstra replaces plain DFS.
You can also watch the flood fill and DFS call stack run cell by cell to see sinking happen in real time.
FAQ
Why sink the grid instead of using a visited set?
Sinking flips each land cell to 0 the instant DFS enters it, which folds "already visited" into the same check you already do for water and out-of-bounds: grid[r][c] === 0. That means no extra O(m·n) boolean[][] or Set, one fewer condition per call, and no way to accidentally re-enter a cell. The only cost is that it destroys the input grid — fine when the caller doesn't need it afterward, and easily avoided by cloning first when they do.
What is the time and space complexity?
Time is O(m · n), where m and n are the grid's dimensions. The outer double loop scans every cell once, and sinking guarantees each cell is entered by DFS at most once, so the recursion adds only linear work overall. Space is O(m · n) in the worst case: a fully-connected land grid produces a single recursion chain whose call stack can hold every cell simultaneously. There's no extra visited structure because the grid itself does that job.
Can I solve this with BFS instead of DFS?
Yes, and the complexity is identical. Replace the recursion with a queue: when the scan finds a 1, push it, sink it, and while the queue is non-empty pop a cell and enqueue any unsunk land neighbors, counting as you go. BFS trades recursion-stack depth for an explicit queue, which avoids stack-overflow risk on very large grids — a practical reason to prefer it when m·n is huge. For interview-sized inputs, DFS is shorter to write and reads more cleanly.
How is this different from Number of Islands?
The traversal is the same flood fill; only the aggregation differs. Number of Islands counts how many times you launch a DFS — it increments a counter once per new island and ignores size. Max Area of Island instead makes each DFS return the size it flooded, then keeps the running maximum across islands. Same scan, same sinking, same neighbors — swap "count the launches" for "measure and compare each flood" and you've converted one problem into the other.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.