Number of Islands: Grid DFS Pattern

You are given a 2D grid of '1's (land) and '0's (water). Count the number of islands. An island is a group of connected '1's surrounded by water, where connections are horizontal or vertical (not diagonal).

This is LeetCode 200: Number of Islands, and it is the single most important grid problem on LeetCode. The pattern it teaches, grid DFS with flood fill, shows up in at least a dozen other problems. If you are going to learn one graph traversal technique, this is the one.

Why this problem matters

Grids are graphs in disguise. Every cell is a node. Every pair of adjacent cells (up, down, left, right) is an edge. Once you see that, "count the islands" becomes "count the connected components," and you can solve it with standard graph traversal.

The flood fill algorithm used here is the same technique used in paint bucket tools, minesweeper auto-reveal, and pathfinding in game maps. It is fundamental, and Number of Islands is the cleanest introduction to it.

The key insight

Scan the grid cell by cell. When you hit a '1' you have not visited yet, you have found a new island. Run DFS (or BFS) from that cell to visit every connected land cell, marking them all as visited so you do not count them again. Increment your island counter by one. Keep scanning until you have checked every cell.

That is the entire algorithm:

1. Loop through every cell in the grid
2. If the cell is '1' and unvisited, increment count and flood-fill from it
3. The flood fill marks all connected land cells as visited
4. Return the count

The DFS solution

def num_islands(grid: list[list[str]]) -> int:
    if not grid:
        return 0

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

    def dfs(r, c):
        # Out of bounds or water? Stop.
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if grid[r][c] != "1":
            return

        # Mark as visited by sinking the island
        grid[r][c] = "0"

        # Explore all four neighbors
        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)

    return count

Let's break this down piece by piece.

The outer loop scans every cell. When it finds a '1', that is a new island. We increment count and call dfs(r, c) to mark the entire island as visited.

The DFS function does three things: checks if the current cell is valid land, marks it as "0" (sinking it), and recurses into all four neighbors. By changing "1" to "0", we ensure we never visit the same cell twice. No separate visited set needed.

Visual walkthrough

Let's trace through a grid with three islands. Watch how the DFS flood fill explores all connected land cells before moving on.

The scan moves left to right, top to bottom. Each time it hits unvisited land, it kicks off a DFS that spreads to every connected land cell. Once the DFS finishes, those cells are all marked as visited (sunk to "0"), so the scan skips over them. Each DFS corresponds to exactly one island.

Why we mark visited in place

People sometimes ask: "Why not use a visited set?" You absolutely can. Here is what it looks like:

def num_islands(grid: list[list[str]]) -> int:
    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:
            return
        if grid[r][c] != "1" 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

This works identically, but uses O(m * n) extra space for the set. The in-place version avoids that by mutating the input grid. In an interview, mention that modifying the input might not be acceptable in production code and offer the visited set as an alternative. Interviewers love hearing that tradeoff.

The BFS alternative

Not a fan of recursion? Use BFS with a queue instead. Same idea, different traversal order.

from collections import deque

def num_islands(grid: list[list[str]]) -> int:
    if not grid:
        return 0

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

    def bfs(r, c):
        queue = deque([(r, c)])
        grid[r][c] = "0"

        while queue:
            row, col = queue.popleft()
            for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                nr, nc = row + dr, col + dc
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == "1":
                    grid[nr][nc] = "0"
                    queue.append((nr, nc))

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1":
                count += 1
                bfs(r, c)

    return count

DFS and BFS both visit every cell in the island exactly once. DFS goes deep before going wide (it follows a path until it dead-ends, then backtracks). BFS goes wide before going deep (it processes all immediate neighbors first, then their neighbors, and so on).

For Number of Islands, both give the same answer. The BFS version has one practical advantage: it avoids deep recursion. If the grid is 300x300 and the entire thing is land, DFS would have a call stack 90,000 frames deep. Python's default recursion limit is 1,000, so that would crash. BFS uses a queue on the heap instead, so no stack overflow risk.

Neighbor generation

Notice how both solutions need to check all four neighbors of a cell. In the DFS version, we wrote four separate recursive calls. In the BFS version, we used a direction array:

for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
    nr, nc = row + dr, col + dc

This "direction array" pattern is a reusable building block for every grid problem. Instead of writing four separate if-statements, you encode the four directions as offset pairs and loop over them. It is cleaner, less error-prone, and extends easily to eight directions (for problems that allow diagonal movement) by adding (1, 1), (1, -1), (-1, 1), (-1, -1).

Complexity analysis

Time is O(m * n) for both approaches, where m is the number of rows and n is the number of columns. Every cell is visited at most once by the outer scan loop, and at most once by a DFS/BFS call. The total work is proportional to the number of cells.

Space is where things get interesting. DFS uses the call stack, and in the worst case (a grid of all '1's), the recursion can go m * n levels deep. BFS uses a queue, and the maximum queue size is bounded by O(min(m, n)) because the BFS frontier in a grid can never be wider than the shorter dimension.

If you use a separate visited set, add O(m * n) to both.

Edge cases

Before submitting, check these:

• Empty grid: return 0. The if not grid check handles this.
• All water: every cell is '0'. The inner if never triggers. Return 0.
• All land: the entire grid is one big island. Return 1. DFS/BFS visits every cell in one pass.
• Single cell: [["1"]] returns 1. [["0"]] returns 0.
• Diagonal-only connection: cells connected only diagonally are not the same island. [["1","0"],["0","1"]] has 2 islands, not 1.

The building blocks

This problem is built on two reusable pieces that CodeBricks drills independently:

1. Grid neighbor generation

The pattern of computing valid neighbors for a cell in a 2D grid:

directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
for dr, dc in directions:
    nr, nc = r + dr, c + dc
    if 0 <= nr < rows and 0 <= nc < cols:
        # (nr, nc) is a valid neighbor

This is the grid equivalent of "get all adjacent nodes" in a graph. You will use it in every single grid problem: flood fill, shortest path in a maze, rotting oranges, surrounded regions, and Pacific Atlantic water flow. The bounds check (0 <= nr < rows and 0 <= nc < cols) prevents index-out-of-range errors. The direction array makes it easy to switch between 4-directional and 8-directional movement.

2. DFS flood fill (explore and mark)

The choose-explore-unchoose skeleton adapted for grids, minus the "unchoose" step because we want to permanently mark cells as visited:

def dfs(r, c):
    if not valid(r, c):
        return
    mark_visited(r, c)
    for each neighbor of (r, c):
        dfs(neighbor)

In backtracking problems, you undo your choice after exploring (choose-explore-unchoose). In flood fill, you skip the unchoose step because you want the visit to be permanent. The cell stays marked. This is the key difference between flood fill and backtracking, and understanding it prevents a common bug where people accidentally unmark cells and get infinite loops.

These two bricks, neighbor generation and flood fill, combine to solve Number of Islands and many related problems. The only thing that changes between problems is what you do when you visit a cell (count it, change its color, compute a distance, etc.).

Common mistakes

1. Forgetting to mark before recursing. If you recurse first and mark later, you can visit the same cell multiple times, leading to infinite recursion. Always mark the cell as visited before exploring its neighbors.

2. Checking visited status only in the outer loop. You need to check it inside the DFS/BFS too. Otherwise, the flood fill revisits cells that were already processed by the current DFS call.

3. Using diagonal neighbors. The problem specifies horizontal and vertical connections only. If you include diagonals, you will merge islands that should be separate.

4. Not handling the empty grid. grid = [] or grid = [[]] should return 0. Accessing grid[0] on an empty list crashes.

When to use this pattern

Look for these signals in a problem:

• You are given a 2D grid (matrix) with cells of different types
• You need to find, count, or measure connected regions
• Movement is defined as horizontal/vertical adjacency
• The problem mentions "connected components," "regions," "areas," or "islands"

Problems that use the same grid DFS/flood fill pattern:

• Surrounded Regions (LeetCode 130): flood fill from the border to mark "safe" regions
• Pacific Atlantic Water Flow (LeetCode 417): flood fill from each ocean inward
• Max Area of Island (LeetCode 695): same as Number of Islands but return the size of the largest one
• Rotting Oranges (LeetCode 994): BFS flood fill with a time component
• Flood Fill (LeetCode 733): literally the algorithm we used, just applied to color changing

From understanding to recall

You have read through the DFS and BFS solutions. You see how flood fill works and why marking visited cells prevents double-counting. But can you write the neighbor generation loop and the DFS function from scratch in an interview?

That is the real test. The pattern has a few details that are easy to forget under pressure: the bounds check order, whether to mark before or after recursing, the direction array syntax. These are not hard concepts. They are recall challenges.

Spaced repetition closes that gap. You practice writing the grid neighbor loop and the flood fill DFS from memory at increasing intervals. After a few rounds, the pattern is automatic. You see a grid problem, and the DFS skeleton flows out without hesitation.

The grid DFS flood fill is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning these individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Maximum Depth of Binary Tree - The simplest DFS recursion problem, a great warm-up before tackling grid DFS
• Longest Consecutive Sequence - Another "find connected components" problem, but in 1D value space instead of a 2D grid
• Climbing Stairs - Teaches the recursive thinking style that makes DFS click

CodeBricks breaks Number of Islands into its grid-neighbor-generation and DFS-flood-fill building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a grid problem shows up in your interview, you do not think about it. You just write it.