4.20.3 — Max Area of Island

LeetCode 695 · Medium

The problem

Return the number of cells in the largest island. Return 0 if there is no land.

0 0 1 0 0
0 0 0 0 0
0 1 1 0 1        →  4    (the three-cell island plus... no —
0 1 0 0 1             the largest here is the pair on the right joined
                      with the one below it: count them per island)

The pattern

4.20.1 Number of Islands with one change: the flood fill returns how many cells it visited, instead of returning nothing.

Each cell contributes 1, plus whatever the four recursive calls contribute. Water and already-visited cells contribute 0.

That is the whole difference, and it is worth noticing how small it is — the flood fill is a template, and problems differ only in what they accumulate while flooding.

The solution

Python

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])

        def area(r: int, c: int) -> int:
            if r < 0 or r >= rows or c < 0 or c >= cols:
                return 0
            if grid[r][c] != 1:
                return 0                     # water, or already counted

            grid[r][c] = 0                   # mark before recursing

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

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

        return best

TypeScript

function maxAreaOfIsland(grid: number[][]): number {
  const rows = grid.length, cols = grid[0].length;

  function area(r: number, c: number): number {
    if (r < 0 || r >= rows || c < 0 || c >= cols) return 0;
    if (grid[r][c] !== 1) return 0;

    grid[r][c] = 0;

    return 1 + area(r + 1, c) + area(r - 1, c)
             + area(r, c + 1) + area(r, c - 1);
  }

  let best = 0;
  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++)
      if (grid[r][c] === 1) best = Math.max(best, area(r, c));

  return best;
}

The 1 + counts this cell; the four calls count the rest of the island.

Marking before recursing is what makes each cell counted exactly once. Marking afterwards would let a cell be reached again through a neighbour and counted twice, and would also loop forever.

best starts at 0, so a grid with no land returns 0 with no special case.

Everything else is identical to 4.20.1.

Complexity

O(rows \times cols) time and space.

The family, made explicit

The flood fill accumulates something. Which something is the whole problem:

problem	the flood returns
Number of Islands	nothing — you count the calls
Max Area of Island	the cell count
Count Sub Islands	whether every cell was also land in a second grid
Number of Closed Islands	whether the island ever touched the border
Number of Distinct Islands	the list of cell offsets, used as a shape fingerprint
Island Perimeter	the number of edges facing water or the outside

Number of Distinct Islands is worth a moment, because it combines two chapters. Two islands are the same if one can slide onto the other, so the fingerprint is the set of cell positions relative to the island's first cell. Record those offsets during the flood, turn them into a tuple, and count the distinct tuples with a set. That is 4.4.4 Group Anagrams's canonical-form move applied to shapes.

What the interviewer will push on

"How is this different from counting islands?" The flood returns a count instead of nothing.

"Why mark before recursing?" Otherwise cells are counted twice and the recursion never ends.

"What if you could not modify the grid?" A separate visited array, same complexity.

"How would you find the largest island you could make by flipping one water cell to land?" That is LeetCode 827, and it is the genuinely interesting follow-up. Flood once, giving each island an id and a size stored in a map. Then for every water cell, look at its four neighbours, collect their distinct island ids, and sum those sizes plus one. The "distinct" is the trap — two neighbours may belong to the same island and must not be double counted. Still O(rows \times cols).

One thing to volunteer: name the family. "This is the flood fill again; the only question in these problems is what you accumulate while flooding." Saying it turns six problems into one.

Next: 4.20.4 Pacific Atlantic Water Flow — where the trick is to run the search backwards.