Max Area of Island

Difficulty: Medium

Problem

You are handed a grid of numbers (not characters) where 1 marks land and 0 marks water. An island is a cluster of land cells linked by shared sides: up, down, left or right. Cells that only touch at a corner are NOT linked. Return the size, in cells, of the biggest island, or 0 if the grid contains no land.

Example

Input: grid = [[1,1,0,0],[1,0,0,1],[0,0,1,1]]
Output: 3
Explanation: There are two islands of equal size: the L-shaped one at top-left {(0,0), (0,1), (1,0)} and the one at bottom-right {(1,3), (2,3), (2,2)}. Each has 3 cells, so the biggest area is 3.

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

Pseudocode

function maxAreaOfIsland(grid):
    best = 0
    
    function area(r, c):
        if out_of_bounds(r, c) or grid[r][c] != 1:
            return ____
        grid[r][c] = ____
        return ____ + area(r-1, c) + area(r+1, c)
                    + area(r, c-1) + area(r, c+1)
    
    for r in 0 .. rows-1:
        for c in 0 .. cols-1:
            best = ____(best, area(r, c))
    
    return best

Hints

  • Off-grid, water, and already-sunk cells add nothing to an island's size. What number says 'I contribute no cells'?
  • Sink the cell BEFORE the four calls go out, so no other call can ever count it. What value drowns land in this grid of numbers?
  • Every report starts with the cell's own worth, then adds the four directional reports: exactly like subtree size in Trees. How much is one cell worth?
  • The scan hears one report per cell and must keep only the LARGEST so far. Which function compares two numbers and keeps the bigger?

Complexity questions

The grid has m rows and n columns. Counting the scan AND all the measuring floods together, what is the total time?

O(m × n): each cell is scanned once and sunk at most once; every touch is constant work. Same accounting as Number of Islands: the loops make m×n calls, and across ALL floods combined each land cell is sunk exactly once, sinking makes it fail the != 1 check forever after. Carrying a return value home costs nothing extra: the flood does the same walk, it just brings a number back.

This solution calls area(r, c) on EVERY cell: even obvious ocean, with no if-guard in the scan. Why is that still O(m × n) total?

A call on water (or sunk land) fails the != 1 check and returns 0 in O(1); only fresh land triggers real work, and each land cell is sunk once ever. Each of the m×n scan calls costs O(1) unless it lands on fresh land, and fresh land immediately stops being fresh, because the flood sinks it. So the total is m×n cheap calls plus at most m×n sink operations across the whole run: O(m × n). The if-guard is a readability choice, not a complexity requirement.

Worst case for the recursive area(): what island shape hurts, and how deep can the call stack go?

One giant snake island winding through every cell. The stack can reach O(m × n) frames before anything returns. Identical to Islands: a serpentine island threading through all m×n cells stacks one frame per cell before any of the additions can start resolving, O(m × n) deep, enough to blow Python's default recursion limit on big grids. A BFS flood with an explicit size counter measures the same island without deep recursion.

New problem: 'given a starting cell (r, c), return the size of the land region CONTAINING it, 0 if it's water.' Which part of today's solution do you keep?

Just the counting flood: return area(r, c) directly, no scan, no best, no max. The scan only existed because we didn't know where the islands were. Handed a starting cell, you skip straight to the measurement: one area(r, c) call floods exactly that region and reports its size, and if (r, c) is water, it returns 0 all by itself. The counting flood was always the reusable part.

Check your understanding of Max Area of Island

You just finished Number of Islands. What actually changes in this sequel?

Instead of counting pieces, we measure each piece and keep the LARGEST, so the flood must now RETURN how many cells it sank. The skeleton is untouched: scan every cell, flood every fresh piece of land. But the question changed from 'how many pieces?' to 'how BIG is the biggest piece?'. So the flood gets a promotion. Instead of returning nothing, each call reports the number of cells it drowned, and the scan keeps the largest report.

How does a recursive flood compute the size of the island it's sinking?

Each call returns 1 (its own cell) plus whatever its four directional calls return. The totals add up on the way back out of the recursion. This is the subtree-size pattern from Trees wearing a grid costume: size = 1 + size(left) + size(right), except a cell has FOUR children, up, down, left, right. On the example, area(0,0) returns 1 + 0 (up) + 1 (down) + 0 (left) + 1 (right) = 3, the whole L-shape, with no counter in sight.

The flood's base cases: off the grid, water, or already sunk. What should they return?

0: those calls contribute no cells to the island. A call that lands off the edge, on water, or on a cell an earlier call already drowned adds nothing to the island, so it reports 0 and vanishes into the sum. That's what makes '1 + up + down + left + right' safe to write: every dead-end direction just adds zero.

Where does best, the answer we're building, actually get updated?

In the SCAN loop: best = max(best, area(r, c)), the flood measures, the scan compares. Same clean division of labor as Islands, one level up: the flood's only job is to measure ONE island and report its size; the scan's job is to compare the reports. Each area(r, c) call comes back with a number, and max keeps the biggest one seen so far. The flood never even knows best exists.

The grid is all water, say [[0,0,0]]. What does maxAreaOfIsland return?

0: best starts at 0, and no flood ever reports more. Every area(r, c) call hits the 'not land' base case immediately and reports 0, so best never rises above its starting value. Initializing best = 0 quietly handles the no-island case, and 0 is exactly what the problem asks for when there's no land.

Related problems

Keep practising