Max Area of Island

Table of Contents +

Max Area of Island is the classic grid question. It tests one core skill. Can you walk a connected blob of cells and count its size without counting any cell twice? Once you can do that, a whole family of grid problems opens up.

🎯 The Problem

You get a grid of 0 and 1. You must find the area of the largest island.

The rules:

A 1 is land. A 0 is water.
An island is a group of land cells joined up, down, left, or right. Diagonals do not count.
The area of an island is the number of land cells in it.
Return the area of the biggest island. If there is no land, return 0.

Here is a small grid.

Input grid:
  0  0  1  0  0
  0  1  1  0  0
  0  0  0  1  1
  0  0  0  1  0

Islands and their sizes:
  - top island (cells [0,2] [1,1] [1,2]) -> size 3
  - bottom island (cells [2,3] [2,4] [3,3]) -> size 3

Output: 3

Each island is a connected component. A connected component is a group of cells you can reach from each other by stepping between land cells. We want the biggest one.

Here is the grid drawn as land cells joined to their neighbors. You can see two separate blobs.

🐢 Approach 1: Count By Hand Without Marking (Brute Force)

This is the messy first attempt that double counts.

The idea:

Scan the grid.
For each land cell, look at its neighbors and try to grow its island by hand.
Add up the land cells you find.

Why it is weak:

The same land cell sits next to several neighbors.
Without a marker, you visit it again from each neighbor.
So your count balloons. The answer is wrong.
You also lose track of which cells you already added.

Here is DFS with a separate visited set:

def max_area_of_island(grid):
    rows, cols, seen = len(grid), len(grid[0]), set()
    def dfs(r, c):
        if r < 0 or c < 0 or r == rows or c == cols or grid[r][c] == 0 or (r, c) in seen:
            return 0
        seen.add((r, c))
        return 1 + dfs(r+1,c)+dfs(r-1,c)+dfs(r,c+1)+dfs(r,c-1)
    return max(dfs(r, c) for r in range(rows) for c in range(cols))

🌊 Approach 2: Flood Fill With DFS (Best)

The idea in one line: start on one land cell, then dive into every connected land cell, marking as you go.

The idea:

Flood fill spreads from a land cell to all connected land cells, like water filling a shape.
DFS (depth first search) dives deep along one direction using recursion, then backs up.

How it works:

Scan the grid cell by cell.
On the first unvisited land cell, start a flood fill from there.
The fill moves into the four land neighbors and counts every cell it touches.
The moment you count a cell, set it to 0. Now it reads as water.
That marking is what stops you from counting any cell twice.
The fill returns the area of one island. Keep the biggest you have seen.

Why it is fast:

Each land cell is visited and marked once.
Time is O(n) in the number of cells.

Here is the in-place flood-fill code:

def max_area_of_island(grid):
    rows, cols = len(grid), len(grid[0])
    def dfs(r, c):
        if r < 0 or c < 0 or r == rows or c == cols or 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)
    return max(dfs(r, c) for r in range(rows) for c in range(cols))

🪣 Approach 3: Flood Fill With BFS (Alternative)

The idea in one line: same flood fill, but spread in rings using a queue instead of recursion.

The idea:

BFS (breadth first search) spreads out layer by layer.
A queue is a line. You add to the back and remove from the front.

How it works:

Push a starting land cell into the queue and mark it.
Pop a cell, count it, then push its unvisited land neighbors.
Repeat until the queue is empty. That is one full island.

Why pick it:

It visits the exact same cells as DFS, so the area is identical.
It avoids deep recursion. So it is safer on a very large island.

Here is a flood fill spreading out from a starting land cell to its connected neighbors.

Steps to Solve

Set the best area to 0.
Walk through every cell in the grid.
When you find a land cell that is not yet visited, start a flood fill from it.
The flood fill marks the cell visited, counts it as one, then floods into the four neighbors that are land and not visited. It adds up all the counts.
Compare the area of this island with the best area so far. Keep the larger one.
After scanning the whole grid, the best area is the answer.

[data-tabs] [role="tablist"], [data-tabs] [data-scroll] { display: none !important; } [data-tabs] [role="tabpanel"] { display: block !important; } [data-tabs] [role="tabpanel"] + [role="tabpanel"] { margin-top: 1rem; }

This Python version uses recursive DFS flood fill and sets visited cells to 0.

grid = [
    [0, 0, 1, 0, 0],
    [0, 1, 1, 0, 0],
    [0, 0, 0, 1, 1],
    [0, 0, 0, 1, 0],
]
R, C = len(grid), len(grid[0])


def dfs(r, c):
    if r < 0 or r >= R or c < 0 or c >= C:   # off the grid
        return 0
    if grid[r][c] == 0:                      # water or already visited
        return 0
    grid[r][c] = 0                           # mark this cell visited
    return 1 + dfs(r + 1, c) + dfs(r - 1, c) + dfs(r, c + 1) + dfs(r, c - 1)


best = 0
for i in range(R):
    for j in range(C):
        if grid[i][j] == 1:                  # start of a new island
            best = max(best, dfs(i, j))
print(best)

The output of the above code will be:

Now let us read the Python version line by line. The dfs function takes a cell and returns the area of the island that cell belongs to.

The first check if r < 0 or r >= R or c < 0 or c >= C: return 0 stops us when the cell is off the grid. We return 0 because there is no land outside the grid. Without this check we would read outside the list and crash.

The second check if grid[r][c] == 0: return 0 stops us on water. It also stops us on a cell we already visited. That is the clever part. The line grid[r][c] = 0 marks a counted cell by turning it into water. So when the search comes back to it, the == 0 check sends it home with 0. This is how we avoid double counting.

The return line 1 + dfs(...) + dfs(...) + dfs(...) + dfs(...) counts the current cell as one, then adds the area found in each of the four directions. The four calls go down, up, right, and left. The sum is the full size of the island.

The main loop scans every cell. When it finds a 1, that is an island we have not seen, so we flood fill it and update best with the larger of the old best and this new area. After the whole grid is scanned, best holds the largest island size.

⏱️ Time and Space Complexity

We touch each cell a small fixed number of times. The scan visits every cell once. The flood fill visits each land cell once and marks it, so it is never revisited. So the total time is O(n), where n is the number of cells. The space is O(n) in the worst case, because a single long island can make the recursion go very deep, or the BFS queue can hold many cells at once.

Approach	Time Complexity	Space Complexity
Count by hand without marking (brute force)	O(n²) and wrong	O(1)
Flood fill with DFS	O(n)	O(n)
Flood fill with BFS	O(n)	O(n)

Tip

Marking a cell the moment you visit it is the whole trick. Set it to 0 or add it to a visited set right away. That one step is what stops you from counting any cell twice.

🧩 Key Takeaways

✅ An island is a connected component of land cells joined up, down, left, or right.
✅ Flood fill spreads from one land cell to all connected land cells and counts them.
✅ Mark each cell visited the moment you count it, so you never count it twice.
✅ DFS uses recursion, BFS uses a queue, and both give the same area.
✅ The whole scan runs in O(n) time, where n is the number of cells.

Check Your Knowledge

4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

🚀 What’s Next?

Surrounded Regions
Rotting Oranges

Previous Pacific Atlantic Water Flow Next Surrounded Regions

Max Area of Island

Follow Us

Follow Us