Max Area of Island

Examples

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

The 1s at (0,2), (1,2), (1,3), (1,4), (2,1), and (2,2) are all connected into one island of 6 cells - that's the biggest (and only) island here.

Input: grid = [[0,0,0,0]]
Output: 0

There's no land, so the largest island has area 0.

Input: grid = [[1,0],[0,1]]
Output: 1

The two 1s only touch diagonally, not horizontally/vertically, so they're two separate islands, each of area 1.

Constraints

• 1 <= rows, cols <= 50

• grid[i][j] is either 0 or 1

Approach

This builds directly on the island-counting idea: scan the grid, and whenever you find an unvisited land cell, spread out to every cell connected to it. The only difference here is what you do with that spread - instead of just marking "an island exists," you count the cells you visit along the way and compare that count against the largest area you've found so far.

With DFS, the natural way to count is to have the function return a number: 1 (for the current cell) plus however many cells each of its neighbors' recursive calls found. With BFS, you can just increment a counter once per cell popped off the queue.

Solutions

DFS - Recursive Area Count

For each unvisited land cell, recursively explore its island and have each call return 1 (for itself) plus the areas returned by its four neighbors. Track the largest area returned across all islands found.

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

  function dfs(r, c) {
    if (r < 0 || r >= rows || c < 0 || c >= cols || 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;
}

Time: O(rows × cols) · Space: O(rows × cols)

BFS - Iterative Area Count

For each unvisited land cell, run a queue-based flood fill and count how many cells get popped off the queue during that one island's exploration - that count is the island's area.

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

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] !== 1) continue;

      let area = 0;
      grid[r][c] = 0;
      const queue = [[r, c]];

      while (queue.length > 0) {
        const [row, col] = queue.shift();
        area++;
        const neighbors = [[row + 1, col], [row - 1, col], [row, col + 1], [row, col - 1]];

        for (const [nr, nc] of neighbors) {
          if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === 1) {
            grid[nr][nc] = 0;
            queue.push([nr, nc]);
          }
        }
      }

      maxArea = Math.max(maxArea, area);
    }
  }

  return maxArea;
}

Time: O(rows × cols) · Space: O(rows × cols)