695. Max Area of Island

Edited by Charles

Medium · Python · Graph

Problem

Read the original problem on LeetCode.

The official page contains the problem statement, examples, and constraints.

Explanation, examples & other approaches

Core idea

Given a binary matrix grid, where

• 1 represents land,
• 0 represents water,

Original study notes follow, including intermediate snippets and earlier attempts.

Idea

Given a binary matrix grid, where

• 1 represents land,
• 0 represents water,

return the maximum area of an island.

An island consists of horizontally or vertically connected land cells.

For example:

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

The output is

5

The key observation is:

Every time we discover an unvisited land cell, we can use Depth-First Search (DFS) to visit the entire island and count its area.

Unlike LeetCode 200, which counts the number of islands, this problem asks us to compute the size of each island and keep the maximum.

The DFS starts from one land cell.

For every visited land cell,

• count the current cell,
• recursively explore its four neighboring cells,
• accumulate the total area.

Every visited land cell is changed into water (0) so that it will never be visited again.

The recursive function receives the current position.

dfs(i, j)

There are three steps.

Step 1: Boundary Check

If

• the position is outside the grid, or
• the current cell is water,

there is no land to contribute.

Return

0

if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] == 0:
    return 0

Step 2: Mark the Current Cell as Visited

Once a land cell is visited,

change it into water.

grid[i][j] = 0

This prevents revisiting the same cell.

Step 3: Compute the Island Area

The current land cell contributes

1

Then recursively add the area from all four directions.

return (
    1
    + dfs(i - 1, j)
    + dfs(i + 1, j)
    + dfs(i, j - 1)
    + dfs(i, j + 1)
)

The returned value is the total area of the current island.

Traverse every cell in the grid.

Whenever an unvisited land cell is found,

grid[i][j] == 1

run DFS.

area = dfs(i, j)

Update the answer.

res = max(res, area)

Continue scanning until every island has been processed.

Consider

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

The grid is

1 1 0
0 1 0
1 0 1

Initially,

Maximum Area = 0

Scan Row 0

The first land cell is

(0,0)

Run DFS.

The connected land cells are

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

The recursive calls return

Area = 3

Update

Maximum Area = 3

The grid becomes

0 0 0
0 0 0
1 0 1

Continue Scanning

The next land cell is

(2,0)

Run DFS.

Only one land cell exists.

Area = 1

The maximum remains

3

Continue Scanning

The next land cell is

(2,2)

Again,

Area = 1

The maximum remains

3

Traversal finishes.

Final answer:

3

Unlike LeetCode 200,

where DFS only marks the island as visited,

here DFS must also compute the island size.

Therefore,

dfs(i, j)

returns

The total number of land cells
belonging to the current island.

Each recursive call contributes

1

for the current cell,

plus the areas returned by its four neighbors.

This naturally accumulates the total island area.

Time Complexity

O(m × n)

Every cell is visited at most once.

Space Complexity

O(m × n)

In the worst case, the recursion stack may contain every cell (when the entire grid is one large island).

Algorithm

Depth-First Search (DFS)

State

Current grid position (i, j)

Visited Mark

grid[i][j] = 0

Return Value

Area of the current island

Search Directions

Up
Down
Left
Right

Main Idea

Whenever an unvisited land cell is found,
run DFS to compute the area of the entire island,
then update the maximum area.

Common Mistakes

• Forgetting to mark a land cell as visited, causing the same island to be counted multiple times.
• Returning nothing from the DFS. In this problem, DFS must return the area contributed by the current island.
• Forgetting to count the current cell.

return 1 + ...

Without the 1, every island area would be underestimated.

• Using diagonal directions. Only the four cardinal directions are considered connected.
• Updating the maximum area inside the DFS. It is clearer to let DFS return the island area first, then update the answer in the outer traversal.
• Confusing this problem with LeetCode 200. The DFS logic is almost identical, but here the recursion returns the accumulated area, whereas in LeetCode 200 it only performs flood fill.

Study record

Field	Value
Attempts	1
Mastery	❚
The Latest Attempt	August 18, 2026

Python solution

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        res = 0

        def dfs(i, j):
            if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] == 0:
                return 0

            grid[i][j] = 0

            return 1 + dfs(i - 1, j) + dfs(i + 1, j) + dfs(i, j - 1) + dfs(i, j + 1)

        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    area = dfs(i, j)
                    res = max(res, area)

        return res

---

Back to Day 44 Graph II · All Algorithm notes