Max Area of Island

The Problem

You are given an m x n binary matrix grid. An island is a group of 1s, representing land, connected horizontally or vertically. You may assume all four edges of the grid are surrounded by 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],
  [1,0,0,0,1,0,0,0,1,0,1,0,0],
  [1,0,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

Example 2:

Input: grid = [[0,0,0,0,0,0,0,0]]
Output: 0

Constraints:

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

The Analogy: Measure One Shoreline Before Comparing It

What are we actually searching for?

We are not trying to count all land squares in the whole map at once. We are trying to measure one connected shoreline at a time, then remember the biggest measurement we have seen.

That changes the job. The moment I step onto a land square, the important question is no longer "is this land?" It becomes "how large is the whole island connected to this square?"

The ranger's measuring walk

Imagine a park ranger flying over a chain of islands with a bundle of survey flags. Every time the ranger lands on fresh land, they walk that entire connected shoreline, dropping one flag on each land square they visit.

The flags do two jobs at once. First, each new flag adds one more unit to this island's area. Second, a flagged square is finished work, so the ranger never measures that square twice.

How we define one shoreline

One shoreline is a connected patch of land reached by walking only up, down, left, or right. Diagonal touching does not count, because the ranger cannot step across corners without passing through water.

So each land square has exactly four meaningful directions to continue the walk:

• up
• down
• left
• right

The property that makes DFS valid

Once the ranger steps onto one square of an island, depth-first search is just a committed measuring walk. Follow one path of land as far as it goes, mark that ground as finished, then backtrack and try the next path.

That works because every square in one island is reachable by repeating those four side steps from some other square in the same island. If I mark a square the moment I measure it, then the only remaining useful work is unvisited neighboring land.

Testing one starting square

When I test a square, there are only three meaningful outcomes:

• it is off the map, so it contributes 0 area
• it is water, so it contributes 0 area
• it is fresh land, so it contributes 1 for itself and may lead to more land around it

That is the whole measuring idea. Every valid land square contributes one unit for itself, then asks its four neighbors whether they also belong to the same shoreline.

How I Think Through This

I think of the DFS helper as "measure the island starting from this square." If the square is useless, off the map or already water, the answer is 0. If it is fresh land, then I already know this island has at least area 1 because I am standing on one real square.

From there I mark that square immediately, then I ask the same measuring question in the four allowed directions. Their returned areas belong to the same shoreline, so I add them onto my current 1. The outer scan does not need to understand island shape, it only needs to compare finished island sizes and keep the largest one.

Take grid = [[1,1,0],[1,0,1]].

Building the Algorithm

Step 1: Teach One Land Square to Contribute Area 1

Start with the smallest real measurement rule. If the coordinates are off the map, or the square is water, this branch contributes no area. If the square is land, mark it visited and return 1.

That single 1 is the foundation of the whole solution. It says, "this square belongs to the island I am measuring, so it counts once." Do not recurse yet. First make one square contribute its own area correctly.

Step 2: Add the Four-Direction Area from the Rest of the Shoreline

Now finish the DFS helper. After marking the current land square, the helper should ask the four side neighbors how much additional area they contribute to the same island.

This is where recursion becomes a measuring tool instead of just a traversal tool. The current square contributes 1, and each recursive call returns extra area from one direction. Add those results together, and the helper returns the full area of the connected shoreline.

Step 3: Scan Every Starting Point and Keep the Largest Island

With the helper complete, the outer function becomes a comparison loop. Walk the whole grid. Whenever you find fresh land, measure that entire island by calling the helper, then compare its returned area against the best answer so far.

The helper turns one starting square into one finished island area. The outer scan only has to remember the maximum. Once an island has been measured, its squares have already been flipped to 0, so later scan positions from that island cannot compete again.

Tracing through an Example

Take grid = [[1,1,0,0],[1,0,0,1],[0,1,1,1]].

Recognizing This Pattern

• Reach for this pattern when the input is a grid or map and the real job is to measure one connected region at a time.
• The structural property is connectivity: once one square in a region is found, repeated side-adjacent moves can reach every other square in that same island.
• DFS flood fill beats restarting local counts from every land square because each cell is processed at most once, and each helper call finishes an entire connected component.

Complete Solution