Max Area of Island

Difficulty: Medium Source: NeetCode

Problem

You are given an m x n binary matrix grid. An island is a group of 1s (representing land) connected 4-directionally (horizontal or vertical). You may assume all four edges of the grid are surrounded by 0s (water).

The area of an island is the number of cells with value 1 in the island.

Return the maximum area of an island in grid. If there is no island, return 0.

Example 1: Input: grid = [[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

Constraints:

• m == grid.length, n == grid[i].length
• 1 <= m, n <= 50
• grid[i][j] is either 0 or 1

Prerequisites

Before attempting this problem, you should be comfortable with:

• DFS / BFS on grids — Number of Islands (LeetCode 200) is the direct predecessor
• Flood fill — marking visited cells while counting them

1. Brute Force (DFS counting)

Intuition

This is Number of Islands with one extra step: instead of just counting islands, we count the area of each island and track the maximum. A DFS function that returns the size of the island it floods is all we need.

Algorithm

1. Initialize max_area = 0.
2. For each unvisited land cell (r, c): run dfs(r, c) which returns the island’s area; update max_area.
3. dfs(r, c): if out of bounds or water or already visited, return 0. Otherwise mark visited and return 1 + dfs(neighbors).
4. Return max_area.

Solution

def maxAreaOfIsland(grid: list[list[int]]) -> int:
    rows, cols = len(grid), len(grid[0])

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != 1:
            return 0
        grid[r][c] = 0  # mark visited by sinking
        return 1 + dfs(r+1,c) + dfs(r-1,c) + dfs(r,c+1) + dfs(r,c-1)

    max_area = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                max_area = max(max_area, dfs(r, c))

    return max_area


grid = [[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]]
print(maxAreaOfIsland(grid))  # 6

print(maxAreaOfIsland([[0,0,0,0,0,0,0,0]]))  # 0

Complexity

• Time: O(M * N) — each cell is visited at most once
• Space: O(M * N) worst-case recursion stack

2. BFS with Area Counter

Intuition

Same logic as DFS but using a queue. For each unvisited land cell, BFS floods the entire island while counting cells. This avoids Python’s recursion depth limit for large grids.

Algorithm

1. For each unvisited land cell, start BFS, mark it visited immediately.
2. Count cells dequeued per BFS run; update max_area.
3. Return max_area.

Solution

from collections import deque

def maxAreaOfIsland(grid: list[list[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    max_area = 0

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                area = 0
                queue = deque([(r, c)])
                grid[r][c] = 0
                while queue:
                    row, col = queue.popleft()
                    area += 1
                    for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
                        nr, nc = row + dr, col + dc
                        if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                            grid[nr][nc] = 0
                            queue.append((nr, nc))
                max_area = max(max_area, area)

    return max_area


grid = [[1,1,0,0,0],[1,1,0,0,0],[0,0,0,1,1],[0,0,0,1,1]]
print(maxAreaOfIsland(grid))   # 4

print(maxAreaOfIsland([[1]]))  # 1

Complexity

• Time: O(M * N)
• Space: O(min(M, N)) — bounded by BFS frontier width

Common Pitfalls

Returning the wrong DFS result. In the DFS approach, each call returns 1 + sum of neighbors. Make sure to return 0 (not 1) for out-of-bounds or water cells — a water cell contributes nothing to area.

Updating max_area before or after DFS. max_area = max(max_area, dfs(r, c)) is correct. If you call dfs first and store the result, that’s fine too — but don’t call dfs twice.

Forgetting the no-island case. The problem says to return 0 if there’s no island. Initializing max_area = 0 handles this correctly.