134. Maximum Island Area

Why this mechanism works

Reuse component traversal but change the aggregation: count each cell visited within the current island, then compare that completed component area with a global maximum. A fresh area counter belongs to each seed, while the visited set belongs to the whole scan.

State and boundaries

area counts popped cells in the active island. best summarizes completed islands. seen prevents overlap between traversals.

Protocol

1. Find an unvisited land seed.
2. Start area at zero and mark the seed.
3. Traverse its component, incrementing area once per cell.
4. Compare the completed area with best.
5. Return best after all seeds.

Visualization

component areas: 2, 1, 4
local area resets at each seed
global best: 2 -> 2 -> 4

Python implementation

def maximum_island_area(grid):
    rows = len(grid)
    cols = len(grid[0]) if rows else 0
    seen = set()
    best = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != 1 or (r, c) in seen:
                continue
            area = 0
            stack = [(r, c)]
            seen.add((r, c))
            while stack:
                x, y = stack.pop()
                area += 1
                for dx, dy in ((1,0),(-1,0),(0,1),(0,-1)):
                    nx, ny = x + dx, y + dy
                    if (0 <= nx < rows and 0 <= ny < cols
                            and grid[nx][ny] == 1 and (nx, ny) not in seen):
                        seen.add((nx, ny))
                        stack.append((nx, ny))
            best = max(best, area)
    return best

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 maximum_island_area: rows = len(grid)
grid=[[1, 1, 0], [0, 1, 0], [1, 0, 1]]; rows=3

L3 maximum_island_area: cols = len(grid[0]) if rows else 0
grid=[[1, 1, 0], [0, 1, 0], [1, 0, 1]]; rows=3; cols=3

L4 maximum_island_area: seen = set()
grid=[[1, 1, 0], [0, 1, 0], [1, 0, 1]]; rows=3; cols=3; seen=set()

L5 maximum_island_area: best = 0
grid=[[1, 1, 0], [0, 1, 0], [1, 0, 1]]; rows=3; cols=3; seen=set(); best=0

L6 maximum_island_area: for r in range(rows):
grid=[[1, 1, 0], [0, 1, 0], [1, 0, 1]]; rows=3; cols=3; seen=set(); best=0; r=0

L7 maximum_island_area: for c in range(cols):
grid=[[1, 1, 0], [0, 1, 0], [1, 0, 1]]; rows=3; cols=3; seen=set(); best=0; r=0; c=0

L10 maximum_island_area: area = 0
grid=[[1, 1, 0], [0, 1, 0], [1, 0, 1]]; rows=3; cols=3; seen=set(); best=0; r=0; c=0; area=0

L11 maximum_island_area: stack = [(r, c)]
grid=[[1, 1, 0], [0, 1, 0], [1, 0, 1]]; rows=3; cols=3; seen=set(); best=0; r=0; c=0; area=0; stack=[(0, 0)]

... 68 intermediate state changes omitted ...

L16 maximum_island_area: for dx, dy in ((1,0),(-1,0),(0,1),(0,-1)):
grid=[[1, 1, 0], [0, 1, 0], [1, 0, 1]]; rows=3; cols=3; seen={(0, 0), (0, 1), (1, 1), (2, 0), (2, 2)}; best=3; r=2; c=2; area=1; stack=[]; x=2; y=2; dx=0; dy=1; nx=1; ny=2

L17 maximum_island_area: nx, ny = x + dx, y + dy
grid=[[1, 1, 0], [0, 1, 0], [1, 0, 1]]; rows=3; cols=3; seen={(0, 0), (0, 1), (1, 1), (2, 0), (2, 2)}; best=3; r=2; c=2; area=1; stack=[]; x=2; y=2; dx=0; dy=1; nx=2; ny=3

L16 maximum_island_area: for dx, dy in ((1,0),(-1,0),(0,1),(0,-1)):
grid=[[1, 1, 0], [0, 1, 0], [1, 0, 1]]; rows=3; cols=3; seen={(0, 0), (0, 1), (1, 1), (2, 0), (2, 2)}; best=3; r=2; c=2; area=1; stack=[]; x=2; y=2; dx=0; dy=-1; nx=2; ny=3

L17 maximum_island_area: nx, ny = x + dx, y + dy
grid=[[1, 1, 0], [0, 1, 0], [1, 0, 1]]; rows=3; cols=3; seen={(0, 0), (0, 1), (1, 1), (2, 0), (2, 2)}; best=3; r=2; c=2; area=1; stack=[]; x=2; y=2; dx=0; dy=-1; nx=2; ny=1

L2 maximum_island_area: rows = len(grid)
grid=[[0, 0]]; rows=1

L3 maximum_island_area: cols = len(grid[0]) if rows else 0
grid=[[0, 0]]; rows=1; cols=2

L4 maximum_island_area: seen = set()
grid=[[0, 0]]; rows=1; cols=2; seen=set()

L5 maximum_island_area: best = 0
grid=[[0, 0]]; rows=1; cols=2; seen=set(); best=0

L6 maximum_island_area: for r in range(rows):
grid=[[0, 0]]; rows=1; cols=2; seen=set(); best=0; r=0

L7 maximum_island_area: for c in range(cols):
grid=[[0, 0]]; rows=1; cols=2; seen=set(); best=0; r=0; c=0

L7 maximum_island_area: for c in range(cols):
grid=[[0, 0]]; rows=1; cols=2; seen=set(); best=0; r=0; c=1

Why the solution is correct

Discovery marking ensures each land cell contributes exactly once to its own component area. Each island is traversed from one seed, so the maximum over completed areas is exactly the largest island size.

Time and space

O(R*C) time and O(R*C) auxiliary space.

Common mistakes

Resetting seen for every seed repeats components. Failing to reset area accumulates multiple islands into one fictitious area.

Reasoning card

Transfer exercise

Compute each island's perimeter by counting land-to-water or land-to-outside edges during the same traversal.