Number of Islands

Hints

1. Recognise the graph. Each '1' is a node; edges connect adjacent '1's. The question "how many connected components?" is the standard graph problem.
2. The traversal pattern. Walk every cell. When you find an unvisited '1', increment the count and launch a DFS/BFS that marks every connected land cell as visited.
3. Two ways to mark visited. A separate boolean grid (O(m·n) extra memory), or mutate the input by setting visited cells to '0' (O(1) extra memory, but destroys the input).
4. DFS vs BFS, same answer, different shape. DFS uses recursion (or an explicit stack); BFS uses a queue. Both are O(m × n).
5. Stack overflow on huge grids. Recursive DFS can hit Python's recursion limit. Iterative DFS with an explicit stack, or BFS, avoids the limit.
6. Union-Find alternative. Treat each '1' as its own component initially; union adjacent '1's. The final number of components equals the island count. O(m × n × α(m × n)), almost linear.

Solution, three approaches

Approach 1 · DFS, O(m × n) time, O(m × n) stack worst case

def num_islands(grid):
    if not grid: return 0
    m, n = len(grid), len(grid[0])
    count = 0

    def dfs(r, c):
        if r < 0 or r >= m or c < 0 or c >= n or grid[r][c] != '1':
            return
        grid[r][c] = '#'                                # mark visited (mutates input)
        dfs(r+1, c); dfs(r-1, c); dfs(r, c+1); dfs(r, c-1)

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

The DFS sinks every cell of one island in a single launch; the outer loop just counts launches. Total work: each cell visited at most a constant number of times. O(m × n).

The mutate-grid trick. Setting visited cells to '#' avoids an auxiliary visited grid. If the caller needs the original grid, copy first.

Stack overflow risk. A 300 × 300 single-island grid has 90,000 cells; recursive DFS in Python overflows around 1000. Either increase the limit (sys.setrecursionlimit) or switch to iterative DFS.

Approach 2 · BFS, O(m × n) time, O(min(m, n)) queue worst case

from collections import deque

def num_islands_bfs(grid):
    if not grid: return 0
    m, n = len(grid), len(grid[0])
    count = 0

    def bfs(start_r, start_c):
        q = deque([(start_r, start_c)])
        grid[start_r][start_c] = '#'
        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 < m and 0 <= nc < n and grid[nr][nc] == '1':
                    grid[nr][nc] = '#'
                    q.append((nr, nc))

    for r in range(m):
        for c in range(n):
            if grid[r][c] == '1':
                count += 1
                bfs(r, c)
    return count

BFS expands in layers, queue size bounded by the perimeter of the BFS frontier, which is O(min(m, n)). On the worst-case "spiral" island this is much less than the recursion depth a DFS would need. The boundedness is what makes BFS robust for large grids.

Approach 3 · Union-Find. O(m × n × α(m × n)) ≈ O(m × n)

Treat each '1' cell as its own component. Sweep the grid; for each '1', union with its left and top neighbours (if they're also '1'). The final component count is the answer.

class DSU:
    def __init__(self, n):
        self.p = list(range(n))
        self.r = [0] * n
        self.count = n

    def find(self, x):
        while self.p[x] != x:
            self.p[x] = self.p[self.p[x]]               # path compression
            x = self.p[x]
        return x

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb: return False
        if self.r[ra] < self.r[rb]: ra, rb = rb, ra
        self.p[rb] = ra
        if self.r[ra] == self.r[rb]: self.r[ra] += 1
        self.count -= 1
        return True

def num_islands_uf(grid):
    m, n = len(grid), len(grid[0])
    dsu = DSU(m * n)
    extra_components = sum(1 for r in range(m) for c in range(n) if grid[r][c] == '0')
    for r in range(m):
        for c in range(n):
            if grid[r][c] != '1': continue
            for dr, dc in ((-1,0), (0,-1)):              # only check left and up
                nr, nc = r + dr, c + dc
                if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == '1':
                    dsu.union(r * n + c, nr * n + nc)
    return dsu.count - extra_components

The DSU answer over-counts because every cell starts as its own component, including water cells. Subtract the water count. The path-compression and union-by-rank make each operation nearly constant amortised; total work is O(m × n × α(m × n)).

Union-Find is worth knowing because it handles a generalisation DFS doesn't: incremental island merging (e.g., "Number of Islands II", where lands are added one at a time). For the basic problem, DFS/BFS are simpler.

Complexity comparison

Edge cases to verify

• Empty grid: guard before the outer loop.
• All water: 0 islands. The outer loop finds no '1's.
• All land: 1 island. The first DFS sinks everything.
• Single cell: 0 if water, 1 if land.
• Diagonal-only connection: two land cells touching at a corner are not the same island under 4-directional connectivity. Be explicit in code reviews; "Number of Islands II" sometimes uses 8-directional.

Where beginners go wrong

• Forgetting to mark cells as visited before launching the traversal. Otherwise the outer loop counts the same island multiple times when it re-encounters cells. Mark immediately on launch and on every recursive entry.
• Using a separate visited grid unnecessarily. Mutating the input to '#' (or '0') saves O(m × n) memory and one allocation. If the caller cares about the input, copy first.
• Recursive DFS on large grids in Python. Default recursion limit is 1000; a 300 × 300 single-island grid blows it up. Either raise the limit or use iterative BFS.
• Checking the grid bounds inconsistently. A single missed boundary check (e.g., negative row index) crashes with IndexError. Centralise the boundary check at the top of the recursive function.
• Treating diagonals as connected when the problem says 4-directional. Read the problem statement; some variants are 8-directional. The neighbour offsets list is the contract.
• Returning the count of land cells instead of islands. The count increments once per launch, not once per cell. The DFS body shouldn't touch the counter.

Interview follow-ups to expect

• "Find the largest island by area." Same traversal, but the DFS returns the cell count of the island it visits. The outer loop tracks the maximum.
• "Surrounded regions, flip all regions completely surrounded by X." Traverse from the boundary inward to mark "escape-connected" regions; everything not marked is surrounded. Same DFS shape, started from a different seed set.
• "Number of distinct islands (by shape)." Compare island shapes via canonical encoding, capture the DFS path string starting from the top-left cell of each island; equal strings mean equal shapes.
• "Number of Islands II, lands are added one at a time." Union-Find is the natural fit. Each addition merges with up to 4 neighbours; track component count incrementally.
• "What if grid is too big to fit in memory?" Process in tiles, using boundary-stitch information for islands spanning multiple tiles. This is a real problem in satellite imagery analysis.

Related reading

• BFS vs DFS (A Decision Guide) the deep-dive that frames the traversal choice.
• Graph Algorithms, the module that puts this problem in context.