LeetCode 695: Max Area of Island

Problem Restatement

We are given an m x n binary matrix grid.

Value	Meaning
`1`	Land
`0`	Water

An island is a group of land cells connected horizontally or vertically.

The area of an island is the number of cells in that connected component.

We need to return the maximum island area in the grid.

If there is no island, return 0. The official statement defines islands using 4-directional adjacency and asks for the largest connected land area. (leetcode.com)

Input and Output

Item	Meaning
Input	Binary matrix `grid`
Output	Maximum island area
Connectivity	Up, down, left, right
Area	Number of land cells

Example function shape:

def maxAreaOfIsland(grid: list[list[int]]) -> int:
    ...

Examples

Example 1:

grid = [
    [0,0,1,0,0],
    [1,1,1,0,0],
    [0,0,0,1,1],
    [0,1,0,1,1],
]

There are multiple islands.

The island:

(0,2)
(1,0)
(1,1)
(1,2)

is connected and has area:

The bottom-right island also has area 4.

Answer:

Example 2:

grid = [
    [0,0,0],
    [0,0,0],
]

There is no land.

Answer:

First Thought: Count Each Island

This is similar to the standard number of islands problem.

When we find a land cell:

grid[r][c] == 1

we can run DFS or BFS to traverse the entire island.

But instead of just counting islands, we count how many land cells belong to the current island.

The largest count is the answer.

Key Insight

DFS naturally computes connected component size.

Suppose DFS visits one land cell.

Then:

Count the current cell as area 1.
Visit all connected neighbors.
Add their areas recursively.

So the DFS return value can be:

Area of the island connected to this cell

Algorithm

Initialize:
```
best = 0
```
Scan every cell in the grid.
When land 1 is found:
- Run DFS.
- DFS returns the island area.
- Update best.
Return best.

DFS steps:

If outside the grid or on water, return 0.
Mark the current land cell as visited.

Return:

1 + dfs(up) + dfs(down) + dfs(left) + dfs(right)

We mark visited cells by changing them from 1 to 0.

Walkthrough

Consider:

grid = [
    [0,0,1,0,0],
    [1,1,1,0,0],
    [0,0,0,1,1],
    [0,1,0,1,1],
]

Start scanning.

At (0,2) we find land.

DFS explores:

(0,2)
(1,2)
(1,1)
(1,0)

Area:

Update:

best = 4

Continue scanning.

Later, another island also has area 4.

The maximum remains:

Return:

Correctness

The DFS starts from an unvisited land cell.

It visits the current cell and recursively visits every horizontally or vertically connected land neighbor.

Because recursion continues through all connected land cells, DFS visits exactly the cells belonging to that island.

Each visited land cell contributes exactly 1 to the total area.

Visited cells are marked as water, so no cell is counted more than once.

Therefore, the DFS return value equals the area of the connected island containing the starting cell.

The outer scan starts DFS once for every island and updates the maximum area seen.

Thus, the algorithm returns the largest island area in the grid.

Complexity

Let:

Symbol	Meaning
`m`	Number of rows
`n`	Number of columns

Metric	Value	Why
Time	`O(m * n)`	Every cell is visited at most once
Space	`O(m * n)` worst case	Recursion stack in a fully connected island

For a sparse grid, recursion depth is smaller.

Implementation

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

        def dfs(r: int, c: int) -> int:
            if r < 0 or r >= rows or c < 0 or c >= cols:
                return 0

            if grid[r][c] == 0:
                return 0

            grid[r][c] = 0

            return (
                1
                + dfs(r + 1, c)
                + dfs(r - 1, c)
                + dfs(r, c + 1)
                + dfs(r, c - 1)
            )

        best = 0

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

        return best

Code Explanation

The helper:

def dfs(r: int, c: int) -> int:

returns the area of the island connected to (r, c).

If the cell is invalid or water:

if grid[r][c] == 0:
    return 0

there is no area contribution.

When we visit land:

grid[r][c] = 0

we mark it visited.

Then we count:

Part	Meaning
`1`	Current cell
`dfs(...)`	Neighbor island area

So:

return (
    1
    + dfs(r + 1, c)
    + dfs(r - 1, c)
    + dfs(r, c + 1)
    + dfs(r, c - 1)
)

computes the full connected component size.

The outer loops scan the whole grid:

for r in range(rows):
    for c in range(cols):

Whenever new land is found:

if grid[r][c] == 1:

we compute that island’s area and update the maximum.

BFS Version

The same problem can also be solved with BFS.

from collections import deque

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

        best = 0

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] != 1:
                    continue

                queue = deque([(r, c)])
                grid[r][c] = 0
                area = 0

                while queue:
                    cr, cc = queue.popleft()
                    area += 1

                    for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
                        nr = cr + dr
                        nc = cc + dc

                        if (
                            0 <= nr < rows
                            and 0 <= nc < cols
                            and grid[nr][nc] == 1
                        ):
                            grid[nr][nc] = 0
                            queue.append((nr, nc))

                best = max(best, area)

        return best

Testing

def run_tests():
    s = Solution()

    grid = [
        [0,0,1,0,0],
        [1,1,1,0,0],
        [0,0,0,1,1],
        [0,1,0,1,1],
    ]
    assert s.maxAreaOfIsland(grid) == 4

    grid = [
        [0,0,0],
        [0,0,0],
    ]
    assert s.maxAreaOfIsland(grid) == 0

    grid = [
        [1],
    ]
    assert s.maxAreaOfIsland(grid) == 1

    grid = [
        [1,1],
        [1,1],
    ]
    assert s.maxAreaOfIsland(grid) == 4

    grid = [
        [1,0,1,0,1],
    ]
    assert s.maxAreaOfIsland(grid) == 1

    print("all tests passed")

run_tests()

Test meaning:

Test	Expected	Why
Mixed grid	`4`	Largest connected component size
All water	`0`	No islands
Single land cell	`1`	Smallest island
Fully connected `2 x 2` island	`4`	Entire grid connected
Separate single-cell islands	`1`	No horizontal connection