Matrix Traversal Pattern: Islands, Flood Fill, and Grid BFS

TL;DR: A grid is a graph whose nodes are cells and whose edges are the neighbouring cells. Say that sentence and the family collapses: Number of Islands becomes counting connected components, Flood Fill becomes one traversal, and Rotting Oranges becomes breadth-first search started from several places at once. You need one helper that yields in-bounds neighbours, one rule for marking cells visited, and one question to decide between depth-first and breadth-first search. The question is whether the problem asks how far, and getting it wrong is the difference between a correct answer and a wrong one.

This is the fifteenth deep dive in our pattern series (the full map lives in the hub), following cyclic sort. Grid problems are among the most common in real interview loops, partly because they are easy to state and partly because they scale smoothly from a warm-up to a genuinely hard question without changing the setup. They also expose one specific bug that produces answers that are close but wrong, which is the worst kind, so we will name it precisely.

The tell: how to recognize a matrix traversal problem

This tell is visual. You are handed a 2D grid, and the cells relate to their neighbours:

• land and water, 1s and 0s, colors, walls and open space
• "count the islands / regions / provinces / enclaves"
• "flood fill", "surrounded regions", "capture what is enclosed"
• "shortest path in a grid", "minimum steps", "fewest moves"
• "how many minutes until everything is infected" (Rotting Oranges)
• "can water flow from here to there"
• "can you reach the exit"

The unifying shape: a cell's meaning depends on the cells next to it, and the question is about connectivity or distance across the whole grid.

The one insight the whole pattern rests on

Here is the sentence that is the pattern: a grid is a graph, and you never have to build it.

In a normal graph problem you receive an edge list and construct an adjacency structure. In a grid the edges are implied by geometry: the neighbours of (r, c) are (r-1, c), (r+1, c), (r, c-1) and (r, c+1), computed on demand. That is the only difference between these problems and the graph problems in topological sort and union-find. Everything else is standard traversal.

So the reusable piece is small:

DIRECTIONS = [(-1, 0), (1, 0), (0, -1), (0, 1)]      # up, down, left, right


def neighbors(r, c, rows, cols):
    for dr, dc in DIRECTIONS:
        nr, nc = r + dr, c + dc
        if 0 <= nr < rows and 0 <= nc < cols:        # bounds check lives here
            yield nr, nc

Putting the bounds check inside the helper means it happens exactly once in your solution instead of being repeated, and repeated bounds checks are where index errors hide. Some problems use eight directions rather than four, so read the statement and add the diagonals when asked.

Template one: depth-first search for connectivity

Counting islands is the canonical form. Walk every cell, and each time you find unvisited land, that is a new island, so increment the counter and then sink the entire landmass so it is never counted again:

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

    def sink(r, c):
        if grid[r][c] != '1':
            return                                   # water, or already visited
        grid[r][c] = '0'                             # mark visited immediately
        for nr, nc in neighbors(r, c, rows, cols):
            sink(nr, nc)

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

The whole idea is in the outer loop: the number of times you have to start a new traversal is the number of connected components. That sentence transfers directly to Max Area of Island, Number of Closed Islands, and Number of Enclaves, which differ only in what sink accumulates or which starting cells are allowed.

Marking visited by writing into the grid is the shortest approach and it destroys the input. If the problem forbids that, keep a separate visited set of coordinates. Either is acceptable; say which you are doing and why.

Template two: breadth-first search for distance

When the question asks how far or how many steps, depth-first search cannot answer it, because the first time it reaches a cell is not necessarily by the shortest route. Breadth-first search visits cells in order of distance, so the first arrival is the shortest one.

Rotting Oranges also introduces the variation worth knowing by name, multi-source BFS: seed the queue with every starting point before the loop begins, and the levels count outward from all of them at once.

from collections import deque


def oranges_rotting(grid):
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c))                 # every rotten cell is a source
            elif grid[r][c] == 1:
                fresh += 1

    minutes = 0
    while queue and fresh:
        for _ in range(len(queue)):                  # one full level = one minute
            r, c = queue.popleft()
            for nr, nc in neighbors(r, c, rows, cols):
                if grid[nr][nc] == 1:
                    grid[nr][nc] = 2                 # mark on PUSH, not on pop
                    fresh -= 1
                    queue.append((nr, nc))
        minutes += 1

    return -1 if fresh else minutes

The for _ in range(len(queue)) line is what separates one level from the next. Snapshotting the length before the inner loop means you process exactly the cells that were already waiting, and anything pushed during the loop belongs to the next level. Without it there is no way to count steps.

The compass: which traversal?

One question decides it: does the problem ask how far?

• No, it asks whether things are connected, how many groups there are, or how large a region is. Use depth-first search. It is shorter, and recursion handles the bookkeeping.
• Yes, it asks for the fewest steps, the shortest path, or a time until something spreads. Use breadth-first search. This is not a preference, it is correctness.
• Several starting points at once. Multi-source BFS: push them all before the loop.
• Edges arrive over time, or you need repeated connectivity queries. Reach for union-find instead, which is built for exactly that.

Want the whole family taught in order? The island and matrix traversal chapter of Grokking the Coding Interview builds from Flood Fill through multi-source BFS and the border-inversion problems, with worked traces and code in six languages, then does the same for all 42 patterns (32 common + 10 advanced).

The escalations interviewers actually reach for

• Flood Fill: the traversal with nothing else attached. A good warm-up and a common phone screen.
• Number of Islands: connected components, and the most asked grid problem there is.
• Max Area of Island: the same traversal returning a size rather than incrementing a counter.
• Surrounded Regions: the inversion trick. Instead of finding enclosed regions, start from the border and mark everything reachable from it as safe, then flip whatever remains. Reframing the question is the difficulty.
• Number of Enclaves and Number of Closed Islands: the same border-first idea in two more costumes.
• Rotting Oranges: multi-source BFS with level counting.
• 01 Matrix: distance from every cell to the nearest zero. Seed the queue with all the zeros at once, which turns a problem that looks like it needs one search per cell into a single pass.
• Walls and Gates: identical to 01 Matrix with the labels changed.
• Pacific Atlantic Water Flow: run the traversal backwards from each ocean's border and intersect the two reachable sets. A strong test of whether you can invert a traversal.
• Word Search: grid traversal with undo, which is really backtracking on a grid.
• Shortest Path in Binary Matrix: BFS with eight directions.

The three mistakes that sink candidates

1. Marking cells visited when they leave the queue instead of when they enter it. This is the bug that produces almost-right answers. If you only mark on pop, the same cell can be pushed several times by different neighbours before it is ever processed, which inflates the queue, breaks the one-level-equals-one-step accounting, and can produce step counts that are too large. Mark the cell the moment you push it.

2. Recursion depth on large grids. A depth-first search over a 1000 by 1000 grid of uniform land recurses a million levels deep and exceeds Python's default limit. If the constraints allow a grid that large, use breadth-first search or an explicit stack, and say why you switched.

3. Mutating the input when the problem does not allow it. Writing into the grid is the neat way to mark visited, and it is wrong when the caller still needs the data. Read the constraints and use a visited set when in doubt.

A fourth worth naming: counting diagonals when the problem says four directions, or missing them when it says eight. Check the statement before writing DIRECTIONS.

Practice ladder

In order, each rung adding one wrinkle.

1. Flood Fill (E): the bare traversal.
2. Number of Islands (M): components by counting traversal starts.
3. Max Area of Island (M): accumulate instead of count.
4. Surrounded Regions (M): start from the border and invert.
5. Rotting Oranges (M): multi-source BFS with levels.
6. 01 Matrix (M): seed every zero at once.
7. Pacific Atlantic Water Flow (M): two reversed traversals, intersected.
8. Word Search (M): traversal with undo.
9. Shortest Path in Binary Matrix (M): eight directions, shortest path.
10. Stretch: Number of Distinct Islands (M), which needs a canonical shape signature.

Then write the tell in your own words ("I should suspect matrix traversal when ___") and move on. Recognition, not volume, is the skill.

The takeaway

One reframing (a grid is a graph whose edges you compute), one helper (in-bounds neighbours, with the check in a single place), two templates (depth-first for connectivity, breadth-first for distance), one question that chooses between them (does it ask how far), one variation worth naming (multi-source BFS, seeded before the loop), and one bug to pre-empt (mark visited on push, never on pop). The full map of where this sits among the other 41 patterns is in the complete pattern guide. Next in the series: 0/1 Knapsack, the first dynamic programming family to learn.

Go deeper: Grokking the Coding Interview teaches all 42 patterns (32 common + 10 advanced) across 300+ sequenced problems, for a one-time $79 with lifetime access. Short on time? Grokking 75 includes the essential grid problems in its 6-week plan.

FAQs

Why is a grid treated as a graph? Because it is one. Each cell is a node and each pair of adjacent cells is an edge. The only difference from a standard graph problem is that you never build an adjacency list, since a cell's neighbours can be calculated from its coordinates.

Should I use DFS or BFS for grid problems? Ask whether the question involves distance. If it asks for the fewest steps, the shortest path, or how long something takes to spread, use BFS, because it reaches every cell by the shortest route first. For counting regions, measuring areas, or testing connectivity, DFS is shorter and equally correct.

What is multi-source BFS? Breadth-first search started from several cells at once. You push every source into the queue before the main loop begins, so the levels expand outward from all of them simultaneously. It turns problems like Rotting Oranges and 01 Matrix into a single pass instead of one search per source.

Why must I mark cells as visited when pushing rather than when popping? Because between the push and the pop, other neighbours can push the same cell again. Marking on push guarantees each cell enters the queue once, which keeps the queue small and preserves the rule that one queue level equals one step, which is what makes the distance count correct.

Are matrix traversal problems asked at FAANG companies? Constantly. Number of Islands is one of the most frequently asked questions anywhere, Rotting Oranges and 01 Matrix are common at Amazon and Google, and Word Search appears regularly at Meta. The family is popular because it scales from an easy warm-up to a hard follow-up without changing the setup.