Max Area of Island: DFS Grid Exploration

You are given a 2D binary grid where 1 represents land and 0 represents water. Find the maximum area of an island in the grid. An island is a group of 1s connected horizontally or vertically, and the area is the number of cells in the island.

This is LeetCode 695: Max Area of Island, and it is a natural follow-up to Number of Islands. Instead of counting how many islands exist, you need to find the biggest one. The core technique is the same: DFS flood fill on a grid. The only twist is tracking the area of each island and keeping a running maximum.

The problem

Given an m x n binary grid, return the area of the largest island. If there is no island, return 0. An island is formed by connecting adjacent land cells horizontally or vertically. You may assume all four edges of the grid are surrounded by water.

The approach

The strategy builds directly on the Number of Islands pattern:

1. Iterate through every cell in the grid
2. When you find a 1 that has not been visited, run DFS from that cell
3. During the DFS, count every land cell you visit. That count is the island's area.
4. After the DFS finishes, compare the area to your running max_area and update if larger
5. Return max_area when the scan is done

The key difference from Number of Islands: your DFS function needs to return a value. Each recursive call returns the number of cells it visited, and you sum them up to get the total area.

The code

def max_area_of_island(grid: list[list[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    max_area = 0

    def dfs(r, c) -> int:
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return 0
        if grid[r][c] != 1:
            return 0

        grid[r][c] = 0

        return 1 + dfs(r + 1, c) + dfs(r - 1, c) + dfs(r, c + 1) + dfs(r, c - 1)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                area = dfs(r, c)
                max_area = max(max_area, area)

    return max_area

The outer loop scans every cell. When it finds a 1, it kicks off a DFS that returns the total area of that island. The DFS marks each cell it visits by setting it to 0 (sinking the island) so it never gets counted twice. Each call returns 1 (for the current cell) plus the areas returned by its four recursive neighbors. Out-of-bounds or water cells return 0, which naturally terminates the recursion.

The line return 1 + dfs(...) + dfs(...) + dfs(...) + dfs(...) is the heart of this problem. It says: "this cell counts as 1, plus however many cells my neighbors contribute." The sum bubbles up through the recursion to give you the total island area.

Complexity analysis

Time is O(m * n) regardless of approach. Every cell is visited at most once by the scan and at most once by a DFS/BFS call.

Space for recursive DFS is O(m * n) in the worst case, when the entire grid is land and the call stack goes as deep as the total number of cells. BFS avoids that deep stack by using a queue, which is bounded by O(min(m, n)) for the frontier width.

Building blocks

Grid DFS

The grid DFS pattern here is identical to Number of Islands, with one addition: the DFS returns the area instead of returning nothing. The building blocks are:

1. Grid neighbor generation: loop over four direction offsets (1,0), (-1,0), (0,1), (0,-1) and bounds-check each neighbor
2. DFS flood fill: visit a cell, mark it, recurse into neighbors. No backtracking since visits are permanent.
3. Accumulate a value during traversal: each DFS call returns 1 + sum(neighbors). This is the new piece. In Number of Islands you just marked cells. Here you count them.

This "return a value from DFS" pattern also shows up in tree problems like Maximum Depth and Diameter of Binary Tree. The idea is the same: each node contributes something, and you combine contributions from children.

Edge cases

• All water: every cell is 0. The DFS never triggers. Return 0.
• Single cell island: [[1]] returns 1. The DFS visits one cell and returns 1.
• Entire grid is one island: all cells are 1. The first DFS call explores everything. The answer equals m * n.
• Multiple islands, same size: the algorithm correctly tracks the max. Ties do not matter since you only need the max area, not which island.
• Single row or single column: the grid is 1D. DFS still works because the direction offsets handle all cases. Only two of the four directions will ever find valid neighbors.

From understanding to recall

You understand the approach: scan the grid, DFS on each unvisited land cell, sum up the area, track the max. But can you write the DFS function from scratch in two minutes? The return-value pattern (return 1 + dfs(...) + dfs(...) + dfs(...) + dfs(...)) is easy to understand but surprisingly easy to fumble under pressure. You might forget to add the 1 for the current cell, or forget to mark visited before recursing.

Spaced repetition solves this. You practice writing the DFS area function from memory at increasing intervals until the pattern is automatic. After a few rounds, you see "find max area in a grid" and the solution flows out without hesitation.

Related posts

• Number of Islands - The foundational grid DFS problem that this one builds on
• Surrounded Regions - Grid DFS from the border inward, a different twist on flood fill
• Pacific Atlantic Water Flow - Multi-source DFS on a grid with two starting boundaries