Max Area of Island

MediumGraphsArrayDFSBFSUnion FindMatrix

Problem

You are given a grid of land and water cells, where land cells connected horizontally or vertically form an island. Instead of just counting islands, return the number of cells in the largest one. If the grid has no land at all, return 0.

Example. In a grid with one four-cell island shaped like a square and one single isolated land cell elsewhere, the answer is 4.

Key idea

This builds on the count-the-islands version of the problem: instead of incrementing a counter each time a new island is found, you need to know how big each island is. The approach is the same flood fill (scan every cell, and when an unvisited land cell turns up, explore its entire connected cluster), but now the exploration returns a value: the number of land cells it touched. Each recursive or queued step contributes one for the current cell plus whatever its unvisited land neighbors contribute, so the flood fill sums up the cluster's size as it goes. After each flood fill finishes, compare its size against a running maximum and keep the larger one. Marking cells visited as they are claimed prevents double-counting a cell across two flood fills and keeps each fill's size confined to that one island.

Solution

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

  function explore(row: number, col: number): number {
    // out of bounds or not unvisited land: contributes no area
    if (row < 0 || row >= rows || col < 0 || col >= cols || grid[row][col] !== 1) {
      return 0;
    }
    grid[row][col] = 0; // mark visited before recursing
    // this cell plus whatever its unvisited neighbors contribute
    return (
      1 +
      explore(row + 1, col) +
      explore(row - 1, col) +
      explore(row, col + 1) +
      explore(row, col - 1)
    );
  }

  for (let row = 0; row < rows; row++) {
    for (let col = 0; col < cols; col++) {
      if (grid[row][col] === 1) {
        maxArea = Math.max(maxArea, explore(row, col)); // keep the largest island seen so far
      }
    }
  }

  return maxArea;
}

Complexity

  • Time: O(rows × cols). Every cell is visited and marked exactly once in total.
  • Space: O(rows × cols). The recursion stack or visited marks can grow to the size of the grid for one giant island.

Watch out for

  • Initialize the running maximum to 0 so an all-water grid correctly reports no island.
  • Mark a cell visited as soon as it is counted, not after recursing further, to avoid loops on cyclic land shapes.
  • Diagonal neighbors do not extend an island; only up-down-left-right connections count toward area.

Pattern

This is the same flood-fill and connected-components scan as Number of Islands, generalized to aggregate a value per component (cell count here) instead of simply counting components. The same idea extends to other per-component properties, such as perimeter.

Related questions