Max Area of Island LeetCode Solution: DFS Cell Counting

Max area of island leetcode problem #695 is one of those problems that feels immediately familiar if you have solved Number of Islands (#200). The grid looks the same, the traversal is the same, and the visited-cell strategy is the same. The only difference is what you track: instead of incrementing a counter each time you start a new DFS, you measure how many cells each DFS visits and keep the maximum.

That single change — returning a count from DFS instead of returning void — transforms "how many islands?" into "how big is the biggest island?" It is a small code change but a meaningful conceptual shift: you are now measuring connected component size, not just detecting connected components.

This walkthrough covers the problem statement, the DFS approach, a visual example, edge cases, and the broader lesson about connected component analysis on grids.

You are given an m x n binary grid where 1 represents land and 0 represents water. An island is a group of 1s connected horizontally or vertically (not diagonally). The area of an island is the number of cells with value 1 in that island. Return the maximum area of an island in the grid, or 0 if there is no island.

This is the natural follow-up to Number of Islands (#200). In #200, you count the total number of distinct islands. Here, you need the size of the largest one. The traversal logic is identical — the difference is purely in what you accumulate during each DFS.

The constraint is m, n up to 50 — a small grid. But the O(m*n) DFS solution is the expected approach regardless of size, and it generalizes to much larger grids without issue.

The approach is straightforward if you know Number of Islands. Iterate over every cell in the grid. When you find a land cell (value 1), launch a DFS from that cell. The DFS explores all connected land cells, marks each as visited by setting it to 0, and returns the total count of cells visited. Compare that count against a running maximum.

The DFS function itself is where the magic happens. For each cell, it checks bounds and whether the cell is land. If not, return 0. Otherwise, mark the cell as visited (set to 0), then recursively explore all four neighbors (up, down, left, right). Return 1 + the sum of all four recursive calls. That "1" counts the current cell, and the recursive calls count everything connected to it.

Time complexity is O(m*n) because every cell is visited at most once — either by the outer loop or during a DFS that marks it as 0. Space complexity is O(m*n) in the worst case for the recursion stack if the entire grid is one island.

The implementation mirrors Number of Islands almost exactly. The outer loop scans every cell. When it finds a 1, it calls the DFS helper and updates the maximum area. The DFS helper does the cell counting.

In pseudocode: initialize maxArea = 0. For each cell (i, j), if grid[i][j] == 1, set maxArea = max(maxArea, dfs(grid, i, j)). The dfs function: if i or j is out of bounds, or grid[i][j] == 0, return 0. Set grid[i][j] = 0 (mark visited). Return 1 + dfs(up) + dfs(down) + dfs(left) + dfs(right).

The key detail is that dfs returns an integer (the area) instead of void. In Number of Islands, dfs just marks cells and returns nothing. Here, each recursive call contributes its count back to the caller. The sum bubbles up to give you the total island area.

This is a textbook example of how a tiny change in return type fundamentally alters what an algorithm computes. Same traversal, same marking strategy, different aggregation.

Consider this grid with two islands. Island A has 4 cells in an L-shape in the top-left corner. Island B has 6 cells forming a block in the bottom-right. The answer is 6.

When the outer loop hits the first land cell of Island A, DFS explores all 4 connected cells, marking each as 0. The DFS returns 4. maxArea becomes 4.

The outer loop continues scanning. When it reaches the first land cell of Island B, DFS explores all 6 connected cells. The DFS returns 6. maxArea updates from 4 to 6.

After the full scan, no more land cells remain (they have all been set to 0). The function returns maxArea = 6. Every cell was visited exactly once — either skipped as water by the outer loop, or explored and zeroed during a DFS.

All water: If the grid contains only 0s, no DFS is ever launched. maxArea stays at 0, which is the correct answer. No special handling needed.

All land: If every cell is 1, the entire grid is one island with area m * n. The first DFS from cell (0, 0) explores every cell and returns m * n. No subsequent DFS launches because all cells are now 0.

Single cell island: A lone 1 surrounded by 0s has area 1. The DFS visits that single cell, returns 1, and maxArea is correctly 1 if no larger island exists.

L-shaped or irregularly shaped islands work perfectly because DFS does not care about shape — it follows all four-directional connections regardless of geometry.

Max Area of Island is about connected component size, not just connected component detection. The same DFS template you use for Number of Islands generalizes to measuring properties of each component — area, perimeter, bounding box, or anything else you can accumulate during traversal.

This is the key takeaway: once you have a DFS that visits every cell in a connected component, you can compute any aggregate property by changing what the DFS returns. Return 1 + recursive sums for area. Return the perimeter contribution for Island Perimeter (#463). Return coordinates for bounding box calculations.

The pattern extends beyond grids. In graph problems, DFS over a connected component can count nodes, sum edge weights, find the diameter, or detect cycles. The traversal is the skeleton — what you attach to it determines the answer.

Practice this problem alongside Number of Islands to cement the pattern. Use YeetCode flashcards to drill the difference: "DFS returns void = count components" vs "DFS returns int = measure component size." That distinction shows up in many grid and graph problems.