Frontend Beauty
ESC

Type to search the knowledge base.

Max Area of Island

Largest 4-connected land component in a grid — DFS/BFS flood fill that returns area, not just count.

intermediate3 min read
  • dsa
  • graph
  • interview
  • Google
  • Meta

The problem

grid[r][c] is 1 (land) or 0 (water). An island is 4-connected land. Return the maximum area (cell count) of any island. No land → 0.

Input:
[[0,0,1,0,0,0,0,1,0,0,0,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,1,1,0,1,0,0,0,0,0,0,0,0],
 [0,1,0,0,1,1,0,0,1,0,1,0,0],
 [0,1,0,0,1,1,0,0,1,1,1,0,0],
 [0,0,0,0,0,0,0,0,0,0,1,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,0,0,0,0,0,0,1,1,0,0,0,0]]
Output: 6

Same framing as Number of Islands — connected components — but track size, not count.

Brute thoughts

Enumerating shapes by hand fails. Flood fill each unvisited land and measure.

Optimal: DFS that returns size

function maxAreaOfIsland(grid: number[][]): number {
  const rows = grid.length;
  if (!rows) return 0;
  const cols = grid[0].length;
  let best = 0;

  function dfs(r: number, c: number): number {
    if (r < 0 || c < 0 || r >= rows || c >= cols) return 0;
    if (grid[r][c] !== 1) return 0;
    grid[r][c] = 0; // visit
    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) {
        best = Math.max(best, dfs(r, c));
      }
    }
  }
  return best;
}

BFS alternative: queue cells, count how many you mark.

function maxAreaBfs(grid: number[][]): number {
  const rows = grid.length;
  if (!rows) return 0;
  const cols = grid[0].length;
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
  let best = 0;

  function bfs(sr: number, sc: number): number {
    const q: [number, number][] = [[sr, sc]];
    grid[sr][sc] = 0;
    let area = 0;
    while (q.length) {
      const [r, c] = q.shift()!;
      area++;
      for (const [dr, dc] of dirs) {
        const nr = r + dr, nc = c + dc;
        if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
        if (grid[nr][nc] !== 1) continue;
        grid[nr][nc] = 0;
        q.push([nr, nc]);
      }
    }
    return area;
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === 1) best = Math.max(best, bfs(r, c));
    }
  }
  return best;
}
Time O(m · n)
Space O(m · n) worst stack/queue

If mutation is forbidden, use a visited matrix instead of writing 0.

Edge cases

  • Empty grid / all water → 0
  • Single land cell → 1
  • Entire grid land → m·n
  • Diagonals only do not connect (4-dir)

Common bugs

  • Returning island count instead of max area
  • Not marking visited → infinite recursion
  • 8-directional neighbors by accident
  • Off-by-one bounds

Interview delivery

  1. Connected components, return max size.
  2. DFS returns 1 + sum of neighbors.
  3. Scan all cells.
  4. O(mn).
  5. Mention BFS if stack depth is a concern.

Further reading