Problem 41 · Graphs

Number of Islands

MediumClassic DSA & systems

01Problem

Given an m x n grid of '1' (land) and '0' (water), return the number of islands, where an island is a group of land cells connected horizontally or vertically.

02Key insight

Each unvisited land cell seeds a flood fill that marks its whole component; the number of seeds is the answer. Use an explicit stack (not recursion) so large grids don't blow the call stack.

03Solution

solution.pypython20 lines

def num_islands(grid: list[list[str]]) -> int:
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    seen: set[tuple[int, int]] = 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:
                cr, cc = stack.pop()
                for nr, nc in ((cr + 1, cc), (cr - 1, cc), (cr, cc + 1), (cr, cc - 1)):
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == "1" and (nr, nc) not in seen:
                        seen.add((nr, nc))
                        stack.append((nr, nc))
    return count

Try it first.

TimeO(m*n)

SpaceO(m*n)

tests.py · 4 passing

tests.pypython4 lines

assert num_islands([]) == 0
assert num_islands([["1","1","0"],["1","0","0"],["0","0","1"]]) == 2
assert num_islands([["0","0"],["0","0"]]) == 0
assert num_islands([["1","0","1","0","1"]]) == 3

04Staff-level follow-up

Grid too big for one machine? Shard into tiles, count islands per tile, then union-find the components touching shared tile borders to dedupe.