Number of Islands

Interview Prep

StandardGraphsgraphsdfsgrid

The problem

Given a 2D grid of '1' (land) and '0' (water), count the islands. An island is a maximal group of land cells connected horizontally or vertically (not diagonally).

Pattern: grid DFS / BFS, mark cells as you go

The classic graph-on-a-grid problem. Each land cell is a node; edges connect to 4-direction neighbors that are also land. The number of islands is the number of connected components.

Sweep the grid in reading order. Each time you find an unvisited land cell, run a flood fill from there to mark every reachable cell, and bump the count by 1. Recognize this pattern any time the question mentions "connected regions" on a grid.

DFS — recursive (in-place marking)

def num_islands(grid: list[list[str]]) -> int:
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])

    def dfs(r: int, c: int) -> None:
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if grid[r][c] != '1':
            return
        grid[r][c] = '#'                # mark visited (in place)
        dfs(r + 1, c); dfs(r - 1, c)
        dfs(r, c + 1); dfs(r, c - 1)

    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                dfs(r, c)
                count += 1
    return count

O(R × C) time. Space is O(R × C) worst case for the recursion stack (a single snake-shaped island fills a stack frame per cell).

Marking visited cells as '#' in place avoids a separate visited set. Acceptable if the interviewer doesn't mind mutating the input — always ask. If they do, use a side set.

BFS — iterative (queue + visited set)

from collections import deque

def num_islands(grid: list[list[str]]) -> int:
    rows, cols = len(grid), len(grid[0])
    seen: set[tuple[int, int]] = set()
    count = 0

    def bfs(r0: int, c0: int) -> None:
        q = deque([(r0, c0)])
        seen.add((r0, c0))
        while q:
            r, c = q.popleft()
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nr, nc = r + dr, c + dc
                if (0 <= nr < rows and 0 <= nc < cols
                        and grid[nr][nc] == '1'
                        and (nr, nc) not in seen):
                    seen.add((nr, nc))
                    q.append((nr, nc))

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1' and (r, c) not in seen:
                bfs(r, c)
                count += 1
    return count

Same time and space, but iterative — useful if the grid could be large enough to blow the recursion stack. The deque-based BFS is safe up to whatever the heap can hold.

Edge cases

Related