Max Area of Island

MediumDFS / GraphsGrid flood fill (connected components via DFS/BFS)dfsgridconnected-components

Maintained by Vikas Dulgunde, software engineer

You receive a rectangular grid where every cell holds either 1 for land or 0 for water. An island is any group of land cells joined to each other through shared edges, so two cells belong to the same island when one sits directly above, below, left, or right of the other. Diagonal contact does not link cells.

The area of an island is simply how many land cells it contains. Your job is to scan the whole grid, identify every separate island, and report the largest area among them.

If the grid holds no land at all, there is no island to measure, so the answer is 0. Otherwise the answer is at least 1, since a lone land cell with water on every side is still an island of area 1.

Examples

Input: [[1,1,1],[1,0,1],[1,1,1]]

Output: 8

Every cell except the center is land, and all eight land cells touch through shared edges around the ring, forming one island of size 8. The single water cell in the middle does not split the ring.

Input: [[1,0,0,1,0],[1,0,0,1,1],[0,0,0,0,0]]

Output: 3

There are two islands. The two stacked land cells on the left form an island of size 2. The cluster on the right (two stacked cells plus one to the right of the lower one) has size 3, so the answer is 3.

Input: [[0,0,0,0,0,0,0,0]]

Output: 0

The grid is all water, so no island exists and the maximum area is 0.

Constraints

m == grid.length, n == grid[0].length
1 <= m, n <= 50
Each grid[i][j] is either 0 (water) or 1 (land).
Cells connect 4-directionally only; diagonal neighbors are not connected.

Visible test cases

maxAreaOfIsland([[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]]) == 6
maxAreaOfIsland([[0,0,0,0,0,0,0,0]]) == 0
maxAreaOfIsland([[1,1,1],[1,0,1],[1,1,1]]) == 8
maxAreaOfIsland([[1,0,0,1,0],[1,0,0,1,1],[0,0,0,0,0]]) == 3
maxAreaOfIsland([[1]]) == 1
maxAreaOfIsland([[0]]) == 0

Hints

Hint 1

When you land on an unvisited 1, you have found the corner of some island. How would you measure the whole island starting from that one cell?

Hint 2

Treat the grid like a graph: each land cell is a node, and edges run to the four orthogonal neighbors that are also land. Flood out from the starting cell, counting cells as you go.

Hint 3

To avoid counting the same cell twice, mark each visited land cell (for example, overwrite it to 0) the moment you reach it. Track the best area seen across all starting cells.

Loading the editor...

Approaches

Depth-first flood fill

Time O(m * n) · Space O(m * n)

Walk every cell once. The first time you touch a land cell that has not been counted, run a flood fill that visits the entire island it belongs to, returns its size, and marks each visited cell so it is never recounted. The answer is the largest size any flood fill returns.

Loop over every cell (r, c) in the grid.
When grid[r][c] is 1, start a depth-first search from that cell.
In the search, if the position is out of bounds or not land, return 0; otherwise set the cell to 0 to mark it visited and return 1 plus the recursive search of its four orthogonal neighbors.
Keep a running maximum of the area returned by each starting search.
After the full scan, return that maximum (0 if no land was ever found).

Breadth-first flood fill (iterative)

Time O(m * n) · Space O(min(m, n))

Same flood-fill idea, but use an explicit queue instead of recursion. This sidesteps deep call stacks if you prefer iteration, while keeping the linear time bound.

Scan every cell; when you find an uncounted land cell, push it onto a queue, mark it 0, and start a counter at 0.
While the queue is non-empty, pop a cell, add 1 to the counter, and push any of its four orthogonal neighbors that are land, marking each as 0 as you enqueue it.
When the queue drains, the counter is that island's area; update the global maximum.
Continue the scan and return the maximum after every cell is handled.

Common mistakes

Forgetting to mark a cell as visited before recursing into its neighbors, which makes the search revisit cells endlessly or count them more than once.
Marking the start cell visited but not checking bounds inside the recursion, leading to index errors at the grid edges.
Returning the count of islands or the area of the first island instead of the maximum area across all islands.
Mutating the caller's grid as a side effect; if the original grid must stay intact, copy it first or keep a separate visited set.
Allowing diagonal moves, which over-merges islands and inflates the answer.

Follow-up variations

Return the count of distinct islands as well as the largest area in a single pass.
Allow 8-directional connectivity (including diagonals) and adjust the neighbor set accordingly.
Solve it without mutating the input grid, using a separate visited structure or a union-find over land cells.
Stream the grid row by row when it is too large to hold in memory and you can only keep two rows at a time.

Build the rest of your prep

All coding problems

Practice problems by company

The NeetCode 150 roadmap

Guide: coding interview patterns

Examples

Input: [[1,1,1],[1,0,1],[1,1,1]]

Output: 8

Every cell except the center is land, and all eight land cells touch through shared edges around the ring, forming one island of size 8. The single water cell in the middle does not split the ring.

Input: [[1,0,0,1,0],[1,0,0,1,1],[0,0,0,0,0]]

Output: 3

Input: [[0,0,0,0,0,0,0,0]]

Output: 0

The grid is all water, so no island exists and the maximum area is 0.

Hints

Hint 1

When you land on an unvisited 1, you have found the corner of some island. How would you measure the whole island starting from that one cell?

Hint 2

Treat the grid like a graph: each land cell is a node, and edges run to the four orthogonal neighbors that are also land. Flood out from the starting cell, counting cells as you go.

Hint 3

To avoid counting the same cell twice, mark each visited land cell (for example, overwrite it to 0) the moment you reach it. Track the best area seen across all starting cells.

Approaches

Depth-first flood fill

Time O(m * n) · Space O(m * n)

Loop over every cell (r, c) in the grid.
When grid[r][c] is 1, start a depth-first search from that cell.
In the search, if the position is out of bounds or not land, return 0; otherwise set the cell to 0 to mark it visited and return 1 plus the recursive search of its four orthogonal neighbors.
Keep a running maximum of the area returned by each starting search.
After the full scan, return that maximum (0 if no land was ever found).

Breadth-first flood fill (iterative)

Time O(m * n) · Space O(min(m, n))

Same flood-fill idea, but use an explicit queue instead of recursion. This sidesteps deep call stacks if you prefer iteration, while keeping the linear time bound.

Scan every cell; when you find an uncounted land cell, push it onto a queue, mark it 0, and start a counter at 0.
While the queue is non-empty, pop a cell, add 1 to the counter, and push any of its four orthogonal neighbors that are land, marking each as 0 as you enqueue it.
When the queue drains, the counter is that island's area; update the global maximum.
Continue the scan and return the maximum after every cell is handled.

Common mistakes

Forgetting to mark a cell as visited before recursing into its neighbors, which makes the search revisit cells endlessly or count them more than once.

Marking the start cell visited but not checking bounds inside the recursion, leading to index errors at the grid edges.

Returning the count of islands or the area of the first island instead of the maximum area across all islands.

Mutating the caller's grid as a side effect; if the original grid must stay intact, copy it first or keep a separate visited set.

Allowing diagonal moves, which over-merges islands and inflates the answer.

Follow-up variations

Return the count of distinct islands as well as the largest area in a single pass.

Allow 8-directional connectivity (including diagonals) and adjust the neighbor set accordingly.

Solve it without mutating the input grid, using a separate visited structure or a union-find over land cells.

Stream the grid row by row when it is too large to hold in memory and you can only keep two rows at a time.

Max Area of Island

Examples

Constraints

Hints

Approaches

Depth-first flood fill

Breadth-first flood fill (iterative)

Common mistakes

Follow-up variations

Recommended problems

Build the rest of your prep

Max Area of Island

Examples

Constraints

Hints

Approaches

Depth-first flood fill

Breadth-first flood fill (iterative)

Common mistakes

Follow-up variations

Recommended problems

Build the rest of your prep