Max Area of Island — DFS Returning Component Size (LC 695)

Problem Statement#

LeetCode 695 — Max Area of Island (Medium)

You are given an m x n binary matrix grid. An island is a group of 1s connected 4-directionally (horizontal or vertical). 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.

Constraints:

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

Example:

Input:
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 1 0 0 0 0 0 0 0
0 1 0 0 1 1 0 0 1 1 1 0 0
0 1 0 0 1 1 0 0 1 0 1 0 0
0 0 0 0 0 0 0 0 0 0 1 0 0
 
Output: 6
Explanation: The island of size 6 is in the bottom-right region.

Why This Problem Matters#

Max Area of Island is the direct evolution of LC 200 Number of Islands and the most-asked grid DFS variant in FAANG interviews after the base counting problem. Where LC 200 only asks "how many components?", this problem asks "how big is the biggest component?" — which forces you to upgrade your DFS from a void flood fill into a function that returns useful information.

This shift teaches a universal interview skill: making your DFS carry data back up the recursion. Once you understand "DFS returns the size of the subtree it explored", you can extend the same template to count perimeters (LC 463), encode shapes (LC 694), and even sum cell values across regions. Google, Meta, and Amazon use this exact problem to gauge whether a candidate truly understands recursion or just memorized the flood fill template.

The Core Insight#

In the basic Number of Islands problem, DFS only needs to mark cells; it does not need to report anything. Here, we need the size of each connected land component. The cleanest formulation is:

The area rooted at cell (r, c) equals 1 (this cell) plus the area returned by DFS on each of its four neighbors.

When DFS hits water, an out-of-bounds index, or an already-visited cell, it returns 0. This base case naturally terminates the recursion and contributes nothing to the sum. The outer loop calls DFS on every unvisited land cell and tracks the running maximum.

The key mental model: DFS is a postorder accumulator. Each recursive call says "give me the size below me", adds 1 for itself, and returns the total to its caller. This is the same pattern you use for tree problems like "diameter of a binary tree" or "count nodes in a subtree".

Why mark in-place? Setting grid[r][c] = 0 after visiting avoids allocating a separate visited matrix. Each cell is processed exactly once across the entire algorithm, giving O(m times n) total work.

Visual Dry Run#

Consider this grid:

1 1 0 0
1 1 0 1
0 0 0 1

Final answer: 4. Notice how the area "bubbles up" through the recursion — each frame adds 1 for its own cell and sums the children's returns.

Solution (Optimal)#

Python#

class Solution:
    def maxAreaOfIsland(self, grid: list[list[int]]) -> int:
        R, C = len(grid), len(grid[0])
 
        def dfs(r: int, c: int) -> int:
            # base case: out of bounds, water, or already visited
            if not (0 <= r < R and 0 <= c < C) or grid[r][c] != 1:
                return 0
            # mark visited by flipping land to water in-place
            grid[r][c] = 0
            # 1 for current cell + areas returned by 4 neighbors
            return (1
                    + dfs(r + 1, c)
                    + dfs(r - 1, c)
                    + dfs(r, c + 1)
                    + dfs(r, c - 1))
 
        best = 0
        for r in range(R):
            for c in range(C):
                if grid[r][c] == 1:           # found unexplored island
                    best = max(best, dfs(r, c))
        return best

JavaScript#

/**
 * @param {number[][]} grid
 * @return {number}
 */
var maxAreaOfIsland = function(grid) {
    const R = grid.length;
    const C = grid[0].length;
 
    // DFS returns the size of the connected component rooted at (r, c)
    function dfs(r, c) {
        if (r < 0 || r >= R || c < 0 || c >= C || grid[r][c] !== 1) return 0;
        grid[r][c] = 0;                       // mark visited
        return 1
             + dfs(r + 1, c)                  // down
             + dfs(r - 1, c)                  // up
             + dfs(r, c + 1)                  // right
             + dfs(r, c - 1);                 // left
    }
 
    let best = 0;
    for (let r = 0; r < R; r++) {
        for (let c = 0; c < C; c++) {
            if (grid[r][c] === 1) {           // unvisited land
                best = Math.max(best, dfs(r, c));
            }
        }
    }
    return best;
};

Time Complexity: O(m times n) — each cell is visited at most once. Space Complexity: O(m times n) worst case for the recursion stack on a fully-land grid.

Common Mistakes#

1. Forgetting to return 0 in the base case. A return (no value) sends back undefined in JS or None in Python, which crashes when added.
2. Initializing best as 1 or -infinity. If no land exists at all, the answer is 0. Initialize best = 0.
3. Comparing strings vs integers. LC 695 uses integer 0/1, unlike LC 200 which uses character '0'/'1'. Mixing these is a classic copy-paste bug.
4. Marking after recursing. If you recurse before flipping the cell to 0, your DFS will revisit and infinite-loop or massively over-count.
5. Treating diagonals as connections. The problem says 4-directional; using 8 directions silently gives wrong answers on small grids.

Interview Tips#

• Lead with the template. Start by drawing the parallel to LC 200: "Same flood-fill skeleton, but DFS returns area instead of void."
• State complexity upfront. O(m times n) time, O(m times n) recursion space. Mention BFS as an alternative if stack depth worries the interviewer.
• Mention immutability. If asked "what if you can't modify input?", switch to a separate visited set without rewriting the algorithm.
• Trace one island. Walk through a 2x2 island with the area returns bubbling up — interviewers love seeing you understand recursion mechanically, not just by template.

Follow-up Questions#

1. What if the grid is too large for recursion (stack overflow)? Convert DFS to an iterative BFS using a queue. Track size as you pop cells off the queue.
2. Return the cells of the largest island, not just the size. Have DFS append (r, c) to a list passed by reference; track the longest list.
3. What if cells have weights and you want max sum, not max count? Replace the literal 1 with grid[r][c] saved before flipping.
4. Streaming version where cells are added one at a time? Use Union-Find with size tracking — the foundation of LC 305 and 827.

Key Takeaways#

• Max Area of Island is the canonical "DFS returns the size of its subtree" problem and an essential FAANG warm-up.
• The recursion mechanic — postorder accumulation — generalizes to perimeter, sum, and shape-encoding problems on grids.
• Marking cells in-place keeps space at O(m times n) without an external visited set.
• Always initialize the running maximum to 0 to handle the empty-island edge case.
• BFS is a drop-in replacement when recursion depth is a concern; the algorithmic complexity is identical.
• Mastering this pattern unlocks LC 463, 694, 827, and 1905 with minimal additional thinking.