Graphs crash course ↗ · 95

695. Max Area of Island

Each island is a connected group of 1s in a binary grid. A DFS flood fill from every unvisited land cell measures its size in O(1) extra work per cell — the max of those sizes is the answer.

● MediumDFSBFSFlood FillConnected ComponentsTypeScript

PROBLEM What we're solving

Given an m × n binary grid of 0s (water) and 1s (land), return the area of the largest island — a 4-directionally connected group of 1s. For the grid:
[[1,1,0,0,0],[1,1,0,0,0],[0,0,0,1,1],[0,0,0,1,1]]
there are two islands, each of area 4, so the answer is 4. If the grid is all water, return 0.

KEY IDEA Flood fill counts the connected component

Insight → a single recursive DFS from any unvisited land cell visits every cell in that island exactly once and returns the count. Mark each visited cell so you never re-enter it. The outer double loop simply fires a fill whenever it hits an un-visited 1. Running max over all fill sizes gives the answer in one pass.

RECIPE Scan → fill → track max

  • 0 · Scan every cell. Iterate r then c. Skip water and already-visited cells — O(m·n) work total, not per island.
  • 1 · Start a flood fill on unvisited land. Call dfs(r, c). This is the seed of a new island.
  • 2 · DFS: mark + recurse. Immediately zero out the current cell (grid[r][c] = 0) so it's never revisited. Recurse in all 4 directions; each out-of-bounds or water call returns 0.
  • 3 · Return area. return 1 + dfs(up) + dfs(down) + dfs(left) + dfs(right) — each live cell contributes exactly 1.
  • 4 · Update max. After each fill, compare with maxArea and keep the larger.
Classic confusion → forgetting to mark the cell before recursing. If you zero it out only on return, the DFS can revisit it via another neighbor and double-count it — or infinite-loop. Zero it out as the first thing inside dfs, before any recursive calls.

COST Complexity & alternatives

Naive: re-scan to measure each island
O(m²·n²)
Find each island, then BFS/DFS it separately — repeated work.
Single flood fill pass
O(m·n)
Every cell visited at most twice (outer scan + DFS). O(m·n) stack space worst case.

BFS variant

Replace the recursive DFS with an iterative BFS using a queue. Identical complexity; avoids call-stack overflow on very large grids (though LeetCode constraints make this academic here). Union-Find also works but adds code without benefit for this problem.

Pattern transfer → flood fill is the engine behind Number of Islands (count components instead of sizing them), Surrounded Regions (fill from border, then flip), Pacific Atlantic Water Flow (two simultaneous fills), and Word Search (DFS on a character grid with backtracking).

RUN IT DFS flood fill each unvisited island

step 0 / 21
STARTScan every cell. When we land on unvisited land, launch a DFS flood fill.
1▶function maxAreaOfIsland(grid: number[][]): number {
2▶  const rows = grid.length;
3▶  const cols = grid[0].length;
4▶  let maxArea = 0;
5 
6  function dfs(r: number, c: number): number {
7    if (r < 0 || r >= rows || c < 0 || c >= cols) return 0;
8    if (grid[r][c] !== 1) return 0;   // water or already visited
9    grid[r][c] = 0;                   // mark visited by zeroing in-place
10    return (
11      1 +
12      dfs(r + 1, c) +
13      dfs(r - 1, c) +
14      dfs(r, c + 1) +
15      dfs(r, c - 1)
16    );
17  }
18 
19  for (let r = 0; r < rows; r++) {
20    for (let c = 0; c < cols; c++) {
21      if (grid[r][c] === 1) {
22        maxArea = Math.max(maxArea, dfs(r, c));
23      }
24    }
25  }
26 
27  return maxArea;
28}
1
1
·
·
·
1
1
·
·
·
·
·
·
1
1
·
·
·
1
1
current area
0
max area
0
current cellactive DFS frontierfully visitedmax recorded
slowfast

TYPESCRIPT The solution, annotated

maxAreaOfIsland.ts
function maxAreaOfIsland(grid: number[][]): number {
  const rows = grid.length;
  const cols = grid[0].length;
  let maxArea = 0;

  function dfs(r: number, c: number): number {
    if (r < 0 || r >= rows || c < 0 || c >= cols) return 0;
    if (grid[r][c] !== 1) return 0;   // water or already visited
    grid[r][c] = 0;                   // mark visited by zeroing in-place
    return (
      1 +
      dfs(r + 1, c) +
      dfs(r - 1, c) +
      dfs(r, c + 1) +
      dfs(r, c - 1)
    );
  }

  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;
}

Reading it block by block

Lines 2–3 — grid dimensions. Capture rows and cols once. maxArea starts at 0; if the grid is all water it stays 0 and is returned as-is.
Lines 6–8 — DFS base cases. Out-of-bounds returns 0. A 0 cell (water or already visited) also returns 0. These two checks are the "wall" that stops the flood fill from spilling.
Line 9 — mark visited immediately. Setting grid[r][c] = 0 before recursing prevents any neighbor from queuing this cell again. This is the in-place visited trick — no extra boolean[][] needed. Caveat: it mutates the input; restore it if the caller expects the grid unchanged.
Lines 10–15 — accumulate area. Return 1(this cell) plus the sum of the four recursive calls. Each call either returns 0 immediately or expands deeper into the island. The total sum bubbles up as the island's area.
Lines 19–23 — outer scan.The nested loops find each island's unvisited seed. Because dfs zeroes every cell it visits, subsequent passes over already-explored land are instant 0-returns — the total work across all DFS calls is still O(m·n).
Complexity → O(m·n) time — every cell is touched at most twice (outer scan + one DFS entry). O(m·n) space in the worst case for the recursive call stack (a single snake-shaped island). Iterative BFS eliminates the stack depth concern.

INTERVIEWFollow-ups they'll ask

  • "Don't mutate the input." Allocate a separate boolean[][] visited array, or clone the grid before running.
  • "Return the actual coordinates of the largest island." Collect [r, c] pairs during the DFS and store the best set alongsidemaxArea.
  • "8-directional connectivity instead of 4?" Add the four diagonal directions to the dirs array — the rest of the code is unchanged.
  • "What if the grid is huge and the stack blows?" Switch to iterative BFS with an explicit queue — same O(m·n) complexity, O(min(m,n)) queue space in practice.
  • "How is this different from Number of Islands?" Number of Islands counts components; this one sizes them and returns the max. The DFS/BFS skeleton is identical — only the accumulator changes.

MNEMONIC The one-liner

"Land found? Dive in, zero it out, count every cell you touch, surface the total."

TRIGGERS When you see ___ → reach for ___

"largest / max connected group of 1s"DFS flood fill returning area
binary grid, 4-directional neighborsrecursive DFS with in-place visited mark
"count islands" or "number of components"flood fill from each unvisited seed
grid traversal, avoid revisitzero-out / visited[][] before recursing

SKELETON The reusable shape

skeleton.ts
function maxAreaOfIsland(grid: number[][]): number {
  const rows = grid.length, cols = grid[0].length;
  let maxArea = 0;

  function dfs(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;                    // mark visited
    return 1 + dfs(r+1,c) + dfs(r-1,c) + dfs(r,c+1) + dfs(r,c-1);
  }

  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;
}

FLASHCARDS Tap to flip

What does one DFS call from a land cell return?
The total area of that connected island — 1 (this cell) + sum of the four recursive returns.
tap to flip
1 / 7
Answer to reveal explanations. No penalty for retries.Score: 0 / 9
QUESTION 01
What is the time complexity of the flood-fill DFS solution?
QUESTION 02
In the DFS, why do we set grid[r][c] = 0 before recursing?
QUESTION 03
For the grid [[1,1,0],[0,1,0],[0,0,1]], what does the algorithm return?
QUESTION 04
What is the worst-case call-stack depth for the recursive DFS?
QUESTION 05
Which of these problems shares the SAME flood-fill DFS skeleton as Max Area of Island?
QUESTION 06
If the grid is entirely 0s, what should the function return?
QUESTION 07
You need to return the island's cells, not just the count. What minimal change is needed?
QUESTION 08
#695 · Max Area of IslandDFS flood-fill: for each unvisited land cell, recursively visit all 4-connected land neighbors, accumulating the component size. Track the global maximum across all islands.Which algorithmic approach does this primarily use?
QUESTION 09
#695 · Max Area of IslandDFS flood-fill: for each unvisited land cell, recursively visit all 4-connected land neighbors, accumulating the component size. Track the global maximum across all islands.Which implementation correctly solves it?