Number of Islands: Flood Fill Pattern Explained

Number of Islands (LeetCode 200) is the most common entry-level graph problem in technical interviews. It appears at Google, Amazon, Facebook, and Microsoft — and it’s the template for an entire family of “flood fill” problems. Master this pattern and you can solve dozens of variants.

Problem

Given a 2D grid of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and formed by connecting adjacent lands horizontally or vertically.

Input:
11110
11010
11000
00000

Output: 1

Input:
11000
11000
00100
00011

Output: 3

Solution: DFS Flood Fill

def num_islands(grid: list[list[str]]) -> int:
    """
    Flood fill: for each unvisited land cell, DFS to mark the whole island as visited.
    Count how many times we start a new DFS = number of islands.
    Time: O(rows * cols), Space: O(rows * cols) for recursion stack
    """
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])
    count = 0

    def dfs(r, c):
        # Base case: out of bounds or water or already visited
        if r = rows or c = cols or grid[r][c] != '1':
            return
        # Mark as visited by sinking the land
        grid[r][c] = '0'
        # Explore all 4 directions
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                dfs(r, c)  # Sink the entire island

    return count

Solution: BFS Flood Fill

Use BFS if the grid is very large and recursion depth limit is a concern:

from collections import deque

def num_islands_bfs(grid: list[list[str]]) -> int:
    """BFS version — no recursion limit issues for large grids."""
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])
    count = 0
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                grid[r][c] = '0'  # Sink immediately to avoid re-queueing
                queue = deque([(r, c)])

                while queue:
                    cr, cc = queue.popleft()
                    for dr, dc in directions:
                        nr, nc = cr + dr, cc + dc
                        if (0 <= nr < rows and 0 <= nc < cols
                                and grid[nr][nc] == '1'):
                            grid[nr][nc] = '0'
                            queue.append((nr, nc))

    return count

Preserve Input: Don’t Modify the Grid

If the interviewer says you cannot modify the grid:

def num_islands_no_modify(grid: list[list[str]]) -> int:
    """Uses a separate visited set instead of modifying grid."""
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])
    visited = set()
    count = 0

    def dfs(r, c):
        if (r = rows or c = cols
                or grid[r][c] == '0' or (r, c) in visited):
            return
        visited.add((r, c))
        dfs(r + 1, c); dfs(r - 1, c)
        dfs(r, c + 1); dfs(r, c - 1)

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

    return count

The Flood Fill Pattern Family

Once you understand Number of Islands, these problems are variants:

Problem	Variation
Max Area of Island (LeetCode 695)	Return max island size instead of count
Surrounded Regions (LeetCode 130)	Flood fill from border; flip non-reachable regions
Pacific Atlantic Water Flow (LeetCode 417)	Multi-source BFS from two borders; find intersection
Number of Provinces (LeetCode 547)	Same pattern but adjacency matrix instead of grid
Flood Fill (LeetCode 733)	Change color of connected region — literal flood fill
Word Search (LeetCode 79)	DFS with backtracking on grid

Union-Find Alternative

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.count = 0  # Number of components

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return
        if self.rank[px]  int:
    """Union-Find approach — useful if asked to handle dynamic land additions."""
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])
    uf = UnionFind(rows * cols)

    # Initialize: count all land cells as separate islands
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                uf.count += 1

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                # Only check right and down to avoid processing edges twice
                for dr, dc in [(1, 0), (0, 1)]:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1':
                        uf.union(r * cols + c, nr * cols + nc)

    return uf.count

The Union-Find approach is preferred when you need to add land cells dynamically (Number of Islands II — LeetCode 305).

Complexity Analysis

Time: O(rows × cols) — each cell is visited at most once
Space: O(rows × cols) — recursion stack in worst case (all land), or visited set