133. Count Islands

Why this mechanism works

A component traversal answers reachability from one seed. To count all components, scan every cell and start a new traversal only from unvisited land. One new seed contributes one island, and its traversal marks the entire component so no later cell counts it again.

State and boundaries

seen contains discovered land cells. count increases once per unvisited land seed, not once per visited cell.

Protocol

1. Scan cells in row-major order.
2. On unvisited land increment count and mark the seed.
3. Explore its four-neighbor land component with a stack.
4. Mark neighbors before pushing.
5. Continue the outer scan.

Visualization

1 0 1
1 0 0
0 0 1
three independent DFS seeds -> three islands

Python implementation

def count_islands(grid):
    rows = len(grid)
    cols = len(grid[0]) if rows else 0
    seen = set()
    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != 1 or (r, c) in seen:
                continue
            count += 1
            seen.add((r, c))
            stack = [(r, c)]
            while stack:
                x, y = stack.pop()
                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))
    return count

Worked execution

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

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

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

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

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

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

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

L10 count_islands: count += 1
grid=[[1, 0, 1], [1, 0, 0], [0, 0, 1]]; rows=3; cols=3; seen=set(); count=1; r=0; c=0

L11 count_islands: seen.add((r, c))
grid=[[1, 0, 1], [1, 0, 0], [0, 0, 1]]; rows=3; cols=3; seen={(0, 0)}; count=1; r=0; c=0

... 51 intermediate state changes omitted ...

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

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

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

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

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

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

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

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

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

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

L10 count_islands: count += 1
grid=[[1, 0], [0, 1]]; rows=2; cols=2; seen=set(); count=1; r=0; c=0

L11 count_islands: seen.add((r, c))
grid=[[1, 0], [0, 1]]; rows=2; cols=2; seen={(0, 0)}; count=1; r=0; c=0

... 22 intermediate state changes omitted ...

L15 count_islands: for dx, dy in ((1,0),(-1,0),(0,1),(0,-1)):
grid=[[1, 0], [0, 1]]; rows=2; cols=2; seen={(0, 0), (1, 1)}; count=2; r=1; c=1; stack=[]; x=1; y=1; dx=0; dy=1; nx=0; ny=1

L16 count_islands: nx, ny = x + dx, y + dy
grid=[[1, 0], [0, 1]]; rows=2; cols=2; seen={(0, 0), (1, 1)}; count=2; r=1; c=1; stack=[]; x=1; y=1; dx=0; dy=1; nx=1; ny=2

L15 count_islands: for dx, dy in ((1,0),(-1,0),(0,1),(0,-1)):
grid=[[1, 0], [0, 1]]; rows=2; cols=2; seen={(0, 0), (1, 1)}; count=2; r=1; c=1; stack=[]; x=1; y=1; dx=0; dy=-1; nx=1; ny=2

L16 count_islands: nx, ny = x + dx, y + dy
grid=[[1, 0], [0, 1]]; rows=2; cols=2; seen={(0, 0), (1, 1)}; count=2; r=1; c=1; stack=[]; x=1; y=1; dx=0; dy=-1; nx=1; ny=0

Why the solution is correct

Each traversal stays inside one island and reaches all its cells. The first scanned cell of each island starts exactly one traversal; all remaining cells are already marked when scanned. Thus the number of seeds equals the number of components.

Time and space

O(R*C) time and O(R*C) visited/worklist space.

Common mistakes

Counting each DFS visit counts land area rather than islands. Eight-neighbor movement merges diagonal islands contrary to the contract.

Reasoning card

Transfer exercise

Record each component's cells or bounding box instead of only counting its seed.