Max Area of Island

1. Problem & Core Objective

Given a binary grid, return the area of the largest island — the number of cells in the largest connected group of 1s. Return 0 if there is none.

0 0 1 0 0 0
0 0 0 0 0 0
0 1 1 0 1 1      →  6      (the 2x3 block on the right)
0 1 1 0 1 1
0 0 0 0 1 1

Constraints: 1 <= m, n <= 50 · cells are 0 or 1

What's actually being tested: the same flood fill as question 1, with the traversal returning a value instead of returning nothing. It's the smallest possible step up, and the point is that the skeleton doesn't change — only what the recursion produces.

2. First-Principles Thought Process

One change from Number of Islands

Question 1's flood returned void — it existed only to mark. Here it returns the size of the component it flooded:

area(r, c) = 1 + area(up) + area(down) + area(left) + area(right)

with out-of-bounds, water, and already-visited cells all returning 0.

That's the same "combine the children's results" shape as the tree recursions in Section 7, applied to a grid.

Why the base cases all return 0

Three conditions produce nothing: off the grid, water, or already counted. Folding them into one guard keeps the recursion uniform:

if (out of bounds || g[r][c] != 1) return 0;

Marking visited cells as 0 makes "water" and "already counted" the same condition — one test covers both. That's why sinking is convenient here even though it mutates the input.

Double-counting is the real risk

If a cell could be counted twice, the area would be wrong. Marking before recursing prevents it: by the time the four recursive calls run, the current cell is already 0, so they can't count it again when they look back.

Marking after the calls would let a neighbour re-enter and recount — and on a 2×2 block that inflates the area immediately.

The outer loop

Same as before: try every cell, flood any unvisited land, and keep the maximum instead of a count.

3. Solution Paths

Approach 1 — Flood, then count separately (brute force)

public int maxAreaOfIsland(int[][] grid) {
    int best = 0;
    boolean[][] visited = new boolean[grid.length][grid[0].length];

    for (int r = 0; r < grid.length; r++)
        for (int c = 0; c < grid[0].length; c++) {
            if (grid[r][c] != 1 || visited[r][c]) continue;
            List<int[]> cells = new ArrayList<>();
            collect(grid, r, c, visited, cells);        // gather the component
            best = Math.max(best, cells.size());        // then measure it
        }
    return best;
}

private void collect(int[][] g, int r, int c, boolean[][] vis, List<int[]> out) {
    if (r < 0 || r >= g.length || c < 0 || c >= g[0].length) return;
    if (g[r][c] != 1 || vis[r][c]) return;
    vis[r][c] = true;
    out.add(new int[]{r, c});
    for (int[] d : DIRS) collect(g, r + d[0], c + d[1], vis, out);
}

• Time O(m · n) · Space O(m · n) for the list plus the stack

Counter-questions on this approach

⭐ "Same complexity. What's wasteful?"

It materialises every cell of the component in a list just to call .size() on it. The traversal already visits each cell exactly once, so it could count them as it goes and never allocate.

That's the difference between a void flood plus bookkeeping, and a flood that returns a value. Same traversal, one fewer data structure.

"Is the allocation actually significant?"

At 50 × 50 it's 2,500 int[] objects worst case — irrelevant. The objection is that it's solving the problem in two steps where one suffices, and the one-step version is shorter.

"When would collecting the cells be justified?"

If you needed the cells themselves — to return the island's shape, compute its perimeter, or compare islands for congruence (which is LeetCode 694). Then the list is the answer, not scaffolding.

Approach 2 — Flood returning the area (optimal)

private static final int[][] DIRS = {{1,0},{-1,0},{0,1},{0,-1}};

public int maxAreaOfIsland(int[][] grid) {
    int best = 0;
    for (int r = 0; r < grid.length; r++)
        for (int c = 0; c < grid[0].length; c++)
            if (grid[r][c] == 1) best = Math.max(best, area(grid, r, c));
    return best;
}

private int area(int[][] g, int r, int c) {
    if (r < 0 || r >= g.length || c < 0 || c >= g[0].length) return 0;
    if (g[r][c] != 1) return 0;                    // water OR already counted

    g[r][c] = 0;                                    // mark BEFORE recursing
    int size = 1;
    for (int[] d : DIRS) size += area(g, r + d[0], c + d[1]);
    return size;
}

Trace — the 2×2 block at rows 2–3, columns 1–2 above:

• Time O(m · n) · Space O(m · n) worst-case recursion depth

Counter-questions on this approach

⭐ "Why mark the cell before the recursive calls rather than after?"

To prevent double-counting. The four calls include the cell I came from, and they'll look back at the current cell. If it's still 1, it gets counted again — and the recursion would also loop forever, bouncing between two adjacent cells.

Marking first makes g[r][c] != 1 true for those calls, so they return 0. On a 2×2 block, marking after the calls reports an inflated area immediately.

⭐ "You mutate the input grid. Does the outer loop still work?"

Yes, and it's what makes the outer loop correct. Once a component is flooded, all its cells are 0, so if (grid[r][c] == 1) skips them. No separate visited array is needed — the mutation is the visited marker.

The cost is destroying the caller's grid. If that's unacceptable I'd use boolean[][] visited and test both conditions separately.

⭐ "Why does one guard cover both water and visited?"

Because sinking a counted cell to 0 makes it indistinguishable from water — and for this algorithm that's exactly right, since both should contribute 0 and stop the recursion.

Collapsing two conditions into one is only safe because the two cases genuinely warrant identical treatment. With a visited array they'd be separate tests.

"What's the stack depth at these constraints?"

50 × 50 = 2,500 cells, so at most 2,500 frames on an all-land grid. That's comfortably within Java's default stack — unlike question 1's 300 × 300, where 90,000 frames would overflow.

So DFS is genuinely safe here, and that's a constraint-specific judgement rather than a general one.

"Why is best initialised to 0 rather than Integer.MIN_VALUE?"

Because 0 is the correct answer for a grid with no land, and an area can never be negative. It's a valid floor, unlike the max-path-sum case in Section 7 where 0 would have been wrong.

Comparison

4. Why the Optimal Wins

Both are linear. The difference is that the optimal version makes the traversal produce the answer rather than producing a data structure that is then measured.

That's the same idea as the value-returning tree recursions: area(cell) = 1 + sum of neighbours' areas, with the base cases returning 0. The grid structure changes nothing about the shape.

The framing worth keeping:

Question 1's flood returned nothing and existed to mark. This one returns a count. Same traversal, same marking discipline — the only change is what the recursion produces.

And the marking rule that makes it correct: mark before recursing, or the cell you came from counts you and you count it back.

5. Java Prerequisites

Value-returning flood fill

private int area(int[][] g, int r, int c) {
    if (outOfBounds || g[r][c] != 1) return 0;
    g[r][c] = 0;                                  // mark FIRST
    int size = 1;
    for (int[] d : DIRS) size += area(g, r + d[0], c + d[1]);
    return size;
}

Sinking as the visited marker — makes "water" and "already counted" one condition, at the cost of mutating the input.

Math.max accumulation — best = Math.max(best, area(...)), initialised to 0 since areas are non-negative.

Stack depth — safe at 50 × 50 (2,500 frames); not safe at 300 × 300.

6. Interview Communication Guide

Clarifying questions: Diagonals connected (no)? May I modify the grid (it decides sink vs visited)? What should an all-water grid return (0)? Grid size (50 × 50 — small enough that DFS recursion is safe)?

The pitch

"This is the island-counting flood fill with one change: the traversal returns the size of the component instead of returning nothing.

So area(r, c) = 1 + the areas of the four neighbours, with out-of-bounds, water, and already-visited all returning 0. That's the same combine-the-children shape as a tree recursion, on a grid.

I mark a cell by sinking it to 0 before recursing. Two reasons that ordering matters. The four calls include the cell I came from, and it will look back at me — if I'm still 1, I get counted twice, and the recursion also bounces between us forever. Marking first makes those calls return 0.

Sinking also means 'water' and 'already counted' become the same condition, so one guard covers both. That's only safe because both genuinely warrant returning 0 and stopping — with a separate visited array they'd be two tests.

The outer loop then tries every cell and keeps the maximum. Because flooded cells are 0, the loop skips them automatically.

O(m·n) time — each cell is flooded once, so the loop and the flood add rather than multiply.

On stack depth: at 50 × 50 the worst case is 2,500 frames, which is safe. At 300 × 300, like the previous question, it would be 90,000 and I'd switch to BFS. That's a constraint-specific call rather than a general rule."

Edge cases to volunteer:

Name the all-water grid and the diagonal case. The first checks the initial value; the second catches an eight-direction neighbour list.

7. Follow-Up Questions — Modified Constraints

⭐ "Return the number of DISTINCT island shapes."

LeetCode 694. Now you need the cells, not just the count — collect each island's coordinates normalised relative to its top-left cell, then put those shape signatures in a Set. This is where the collect-the-cells approach stops being wasteful and becomes necessary.

⭐ "What's the largest island you could make by flipping ONE 0 to 1?"

LeetCode 827. Two passes: label every island with an id and record its area, then for each 0 sum the areas of its distinct neighbouring island ids and add one. The "distinct" matters — two neighbours may belong to the same island and would otherwise be double-counted. O(m·n).

"Return the island's perimeter instead of its area."

Each land cell contributes 4 − (number of land neighbours). Computed in the same flood by adding that instead of 1.

"What if the grid were too large to hold in memory?"

Stream it row by row with union-find over a two-row window, merging component labels as rows scroll past and keeping a running size per label. O(m·n) time, O(n) memory — the standard connected-component labelling approach.

"Count islands of area exactly k."

Same flood; compare the returned area to k and increment a counter. The return value makes this a one-line change, which the collect-and-measure version would also handle but with more machinery.

"What if cells had weights and you wanted the heaviest island?"

Return g[r][c] + sum of neighbours instead of 1 + …. But then sinking to 0 no longer marks it — a weight of 0 is legitimate land. You'd need a separate visited array, which shows the sink trick depends on 0 being outside the land values.