Max Area of Island

Difficulty: Medium

Problem

You are given a grid where every cell is either 1 (land) or 0 (water) — numbers this time, not characters. Return the AREA of the largest island: the number of cells in the biggest group of 1s connected 4-directionally (up, down, left, right). Diagonal touching still does NOT connect land. If the grid has no land at all, return 0.

Example

Input: grid = [[1,1,0,0],[1,0,0,1],[0,0,1,1]]
Output: 3
Explanation: Two islands tie at 3 cells each: the L-shaped piece top-left {(0,0), (0,1), (1,0)} and the corner piece bottom-right {(1,3), (2,3), (2,2)}. The largest area is 3 either way.

Brute-force approach

There is no separate brute force worth writing — the counting flood IS the natural solution. (The 'worse' version, measuring each island without sinking anything, bounces between two adjacent land cells forever.)

Optimal approach

Key insight: The flood doesn't just sink the island — every call reports 1 + whatever its four neighbors report. The island measures itself on the way back up the recursion.

Scan every cell and call area(r, c) on it. Water reports 0 instantly; fresh land triggers a flood that sinks the whole island while adding up its cells — each call returns 1 plus its four neighbors' reports. The scan keeps the maximum report as best.

Steps

  1. Scan the grid row by row, left to right
  2. Call area(r, c) on every cell — water and already-sunk cells report 0 in O(1)
  3. On fresh land: sink the cell first, then return 1 + area(up) + area(down) + area(left) + area(right)
  4. The sums roll back up the recursion, so the scan's call receives the whole island's size
  5. best = max(best, area(r, c)) after every call — when the scan finishes, best is the answer

Time complexity: O(rows × cols) · Space complexity: O(rows × cols) worst-case recursion