Max area of island: flood-fill connected component sizing

Coding Challenges
1

Problem. In a binary grid, return the area of the largest connected region of 1s using 4-directional adjacency.

This is the classic grid DFS for component area pattern.

Examples:

  • A grid containing one 6-cell island and smaller islands → 6
  • A grid of all 0s → 0
  • A single 1 cell → 1

Solution. Every unvisited land cell can start a DFS or BFS that counts the full size of its connected component. Track the largest such component size.

def max_area_of_island(grid):
    rows = len(grid)
    cols = len(grid[0])

    def dfs(row, col):
        if row < 0 or row >= rows or col < 0 or col >= cols or grid[row][col] == 0:
            return 0
        grid[row][col] = 0
        return 1 + dfs(row + 1, col) + dfs(row - 1, col) + dfs(row, col + 1) + dfs(row, col - 1)

    best = 0
    for row in range(rows):
        for col in range(cols):
            if grid[row][col] == 1:
                best = max(best, dfs(row, col))
    return best

O(mn) time, O(mn) worst-case recursion stack in a full-land grid.

Gotchas.

  • Mark visited land so it is not counted twice.
  • Adjacency is only up, down, left, and right unless the prompt explicitly allows diagonals.
  • If mutating the input grid is undesirable, use a separate visited set.

Run: Max Area Of Island