# Number of Islands: Flood Fill Pattern Explained

Source: https://www.techinterview.org/post/3233460121/number-of-islands-flood-fill-pattern-explained/
Updated: 2026-07-05 · techinterview.org

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 < 0 or r >= rows or c < 0 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 < 0 or r >= rows or c < 0 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] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        self.count -= 1


def num_islands_union_find(grid: list[list[str]]) -> 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

## Related Graph Topics
- [BFS vs DFS: When to Use Each](https://www.techinterview.org/post/3233460119/bfs-vs-dfs-when-to-use-each-with-examples/) — Number of Islands uses DFS flood fill; BFS version avoids recursion limits on large grids; understand when to use each
- [Detect a Cycle in a Graph](https://www.techinterview.org/post/3233460120/detect-a-cycle-in-a-graph-directed-and-undirected/) — Union-Find appears in both: the grid-based Union-Find solution here extends to cycle detection in undirected graphs