Matrix Traversal Patterns

A matrix is just a 2D grid of values — a list of lists in Python — and a huge slice of coding interview problems (image rotation, flood fill, island counting, shortest path on a grid, Conway’s Game of Life) boil down to one skill: visiting the cells of that grid in the right order. Matrix traversal patterns are the small set of reusable techniques for doing that: plain row-major scanning, spiral/boundary walks, and graph-style BFS/DFS where each cell is a node connected to its neighbors. Master these and a large category of \”grid problems\” stops looking scary and starts looking like the same four or five moves applied to a new shape.

Overview / How It Works

Think of a matrix as a two-dimensional array with rows rows and cols columns, where a cell is addressed by matrix[row][col]. There are three broad families of traversal you’ll see over and over:

1. Row-major (or column-major) traversal. Two nested loops, one over rows and one over columns, visiting every cell exactly once in reading order. This is the default for tasks like summing all elements, applying a transform to every cell, or building a new matrix from an old one.

2. Ordered/geometric traversal. The order of visiting matters and follows the matrix’s geometry rather than simple row-major order: spiral traversal (peel the matrix like an onion, layer by layer), diagonal traversal (walk along diagonals), or boundary traversal (just the outer ring). These are usually implemented by tracking shrinking boundaries — top, bottom, left, right — that close in toward the center.

3. Graph-style traversal (BFS/DFS on a grid). A matrix can be treated as an implicit graph where each cell is a node and its up/down/left/right (sometimes diagonal) neighbors are its edges. This is how you solve flood fill, number of islands, shortest path in a maze, and \”rotting oranges\”-style problems. Instead of an adjacency list, you generate neighbors on the fly with a small list of direction offsets, and you track which cells have already been visited so you don’t loop forever or recount the same region.

The reason a directions list of (delta_row, delta_col) tuples shows up in almost every grid solution is that it turns four (or eight) near-duplicate if-blocks into one small loop — and it makes it trivial to switch from 4-directional movement (up/down/left/right) to 8-directional (adding the diagonals) by adding four more tuples.

Time and Space Complexity

Almost every matrix traversal pattern touches each cell a bounded number of times, so the baseline complexity for \”visit everything once\” is O(rows × cols), commonly written O(m × n) or, for a square matrix, O(n²). The table below breaks down the patterns covered in this lesson.

Pattern	Time	Space	Why
Row-major traversal	O(rows × cols)	O(1) extra	Two nested loops visit every cell exactly once; no auxiliary structure needed.
Spiral / boundary traversal	O(rows × cols)	O(rows × cols) for the output list, O(1) extra otherwise	Four shrinking boundaries still touch each cell exactly once in total, across all layers combined.
Grid BFS / DFS (flood fill)	O(rows × cols)	O(rows × cols)	Each cell is enqueued/pushed and marked visited at most once; the visited set plus queue/stack can hold up to every cell in the worst case.
In-place rotation (n × n)	O(n²)	O(1) extra	Transpose touches each of the n² cells once, then each of the n rows is reversed in place.

Note what the variable actually measures: for a matrix, that’s rows × cols (total number of cells), not just one dimension — a traversal of a 1000×1 matrix and a 1×1000 matrix are both O(1000), even though they look very different.

Examples

Example 1: Basic row-major traversal

The simplest pattern: visit every cell in reading order. This is the building block everything else is compared against.

def traverse_matrix(matrix: list[list[int]]) -> None:
    rows = len(matrix)
    cols = len(matrix[0]) if rows > 0 else 0
    for row in range(rows):
        line = []
        for col in range(cols):
            line.append(str(matrix[row][col]))
        print(\" \".join(line))

matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9],
]
traverse_matrix(matrix)

Output:

1 2 3
4 5 6
7 8 9

Each pass through the outer loop handles one row; the inner loop builds that row’s values as strings and joins them with spaces before printing. Since every cell is touched exactly once and the work per cell is O(1), the whole thing is O(rows × cols) time and O(1) extra space (the line list is discarded and rebuilt each row, never growing past cols in size).

Example 2: Spiral traversal

Spiral order visits the outer ring first (left-to-right along the top, top-to-bottom along the right, right-to-left along the bottom, bottom-to-top along the left), then repeats on the next ring in. It’s tracked with four shrinking boundaries instead of a fixed row/col loop.

def spiral_order(matrix: list[list[int]]) -> list[int]:
    if not matrix or not matrix[0]:
        return []

    result: list[int] = []
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1

    while top <= bottom and left <= right:
        for col in range(left, right + 1):
            result.append(matrix[top][col])
        top += 1

        for row in range(top, bottom + 1):
            result.append(matrix[row][right])
        right -= 1

        if top <= bottom:
            for col in range(right, left - 1, -1):
                result.append(matrix[bottom][col])
            bottom -= 1

        if left <= right:
            for row in range(bottom, top - 1, -1):
                result.append(matrix[row][left])
            left += 1

    return result

matrix = [
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9, 10, 11, 12],
]
print(spiral_order(matrix))

Output:

[1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]

The top row is read left-to-right (1 2 3 4), then top moves down. The right column is read top-to-bottom, skipping the corner already used (8 12), then right moves left. The bottom row is read right-to-left (11 10 9), guarded by if top <= bottom so a matrix with only one row left doesn’t get double-counted. The left column is read bottom-to-top (5), guarded by if left <= right for the same reason. The boundaries have now closed in enough that only the middle two cells remain, which the next loop iteration picks up as 6 7.

Example 3: Grid BFS — counting islands

Treat the grid as a graph: each \"1\" cell is connected to its orthogonal \"1\" neighbors, and a \”visit everything reachable from here\” pass (a flood fill) finds one whole island at a time.

from collections import deque

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

    rows, cols = len(grid), len(grid[0])
    visited: set[tuple[int, int]] = set()
    islands = 0
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    def bfs(start_row: int, start_col: int) -> None:
        queue = deque([(start_row, start_col)])
        visited.add((start_row, start_col))
        while queue:
            row, col = queue.popleft()
            for delta_row, delta_col in directions:
                next_row, next_col = row + delta_row, col + delta_col
                in_bounds = 0 <= next_row < rows and 0 <= next_col < cols
                if in_bounds and (next_row, next_col) not in visited and grid[next_row][next_col] == \"1\":
                    visited.add((next_row, next_col))
                    queue.append((next_row, next_col))

    for row in range(rows):
        for col in range(cols):
            if grid[row][col] == \"1\" and (row, col) not in visited:
                islands += 1
                bfs(row, col)

    return islands

grid = [
    [\"1\", \"1\", \"0\", \"0\"],
    [\"1\", \"0\", \"0\", \"1\"],
    [\"0\", \"0\", \"1\", \"1\"],
    [\"0\", \"0\", \"0\", \"0\"],
]
print(num_islands(grid))

Output:

2

The outer double loop scans row-major order looking for an unvisited \"1\". It finds one at (0, 0), increments islands to 1, and BFS floods outward, marking (0, 0), (1, 0), and (0, 1) visited (that whole top-left blob is one island; note (1, 1) is \"0\", so the flood stops there). The scan continues and finds the next unvisited \"1\" at (1, 3), increments islands to 2, and floods to (2, 3) and (2, 2). No more unvisited \"1\" cells remain, so the final count is 2.

How It Works Step by Step

Walking through Example 2’s spiral traversal on its 3×4 matrix, boundary by boundary:

1. Start: top=0, bottom=2, left=0, right=3. Loop condition holds.
2. Read top row (row=0, columns 0→3): appends 1, 2, 3, 4. top becomes 1.
3. Read right column (col=3, rows 1→2): appends 8, 12. right becomes 2.
4. top (1) <= bottom (2) is true, so read the bottom row (row=2, columns 2→0): appends 11, 10, 9. bottom becomes 1.
5. left (0) <= right (2) is true, so read the left column (col=0, rows from bottom (1) down to top (1), i.e. just row 1): appends 5. left becomes 1.
6. Loop check: top=1, bottom=1, left=1, right=2 — still valid, so a second layer runs. Top row (row=1, columns 1→2): appends 6, 7. top becomes 2.
7. Right column: the range for rows top(2) to bottom(1) is empty, nothing appended. right becomes 1.
8. top (2) <= bottom (1) is now false, so the bottom-row and left-column reads are skipped this round.
9. Loop check: top=2, bottom=1 — top <= bottom is false, loop ends.

Final result: [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7] — exactly what the code printed.

Common Mistakes

1. Forgetting the lower bound — Python silently wraps negative indices

A classic grid bug: checking only the upper bound when validating a neighbor. In most languages this throws an out-of-bounds error you’d immediately notice. In Python, a negative index doesn’t error — it silently wraps around to the end of the list, quietly corrupting your traversal.

def get_neighbors(grid, row, col):
    rows, cols = len(grid), len(grid[0])
    neighbors = []
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    for delta_row, delta_col in directions:
        next_row, next_col = row + delta_row, col + delta_col
        if next_row < rows and next_col < cols:  # BUG: no lower-bound check
            neighbors.append(grid[next_row][next_col])
    return neighbors

Called on cell (0, 0) of a 3×3 grid, the up-neighbor offset gives next_row = -1. The check next_row < rows (-1 < 3) passes, so grid[-1][0] is read — which Python happily resolves to the last row instead of raising an error. The fix is to require both bounds, and put them in the same expression so Python’s chained comparison reads naturally:

def get_neighbors(grid: list[list[int]], row: int, col: int) -> list[int]:
    rows, cols = len(grid), len(grid[0])
    neighbors = []
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    for delta_row, delta_col in directions:
        next_row, next_col = row + delta_row, col + delta_col
        if 0 <= next_row < rows and 0 <= next_col < cols:
            neighbors.append(grid[next_row][next_col])
    return neighbors

grid = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9],
]
print(get_neighbors(grid, 0, 0))

Output:

[4, 2]

Now the up- and left-neighbors of (0, 0) are correctly rejected, leaving only the real neighbors: grid[1][0] = 4 and grid[0][1] = 2.

2. Marking visited too late in BFS

If you only check and mark visited when a cell is dequeued rather than when it’s enqueued, the same cell can be pushed onto the queue several times (once from each neighbor that reaches it before it’s processed) before it’s ever checked. The algorithm still terminates, but it does extra work and holds more duplicate entries in the queue than necessary — a subtle performance bug that gets worse as regions get larger.

def bfs_wrong(grid, start):
    rows, cols = len(grid), len(grid[0])
    queue = deque([start])
    visited = set()
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    while queue:
        row, col = queue.popleft()
        if (row, col) in visited:
            continue
        visited.add((row, col))
        for delta_row, delta_col in directions:
            next_row, next_col = row + delta_row, col + delta_col
            if 0 <= next_row < rows and 0 <= next_col < cols and grid[next_row][next_col] == 1:
                queue.append((next_row, next_col))
    return visited

The fix: mark a cell visited the moment you decide to enqueue it, so it can never be added a second time.

from collections import deque

def bfs_correct(grid: list[list[int]], start: tuple[int, int]) -> set[tuple[int, int]]:
    rows, cols = len(grid), len(grid[0])
    queue = deque([start])
    visited = {start}
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    while queue:
        row, col = queue.popleft()
        for delta_row, delta_col in directions:
            next_row, next_col = row + delta_row, col + delta_col
            in_bounds = 0 <= next_row < rows and 0 <= next_col < cols
            if in_bounds and (next_row, next_col) not in visited and grid[next_row][next_col] == 1:
                visited.add((next_row, next_col))
                queue.append((next_row, next_col))
    return visited

grid = [
    [1, 1, 0],
    [0, 1, 0],
    [0, 1, 1],
]
print(sorted(bfs_correct(grid, (0, 0))))

Output:

[(0, 0), (0, 1), (1, 1), (2, 1), (2, 2)]

Each cell now enters visited exactly once, at enqueue time, so it can never be pushed onto the queue twice — this is what actually gives BFS its clean O(rows × cols) bound.

3. Mutable default arguments in recursive grid helpers

Recursive traversal helpers that accumulate results are tempting to write with a default list argument. But Python evaluates default argument values once, when the function is defined — not on every call — so a mutable default like [] is silently shared and reused across every call that doesn’t pass its own list explicitly.

def collect_path(grid, row, col, path=[]):  # BUG: mutable default argument
    path.append((row, col))
    if col + 1 < len(grid[0]):
        collect_path(grid, row, col + 1, path)
    return path

A second, unrelated call to collect_path without an explicit path would start with whatever was left over from the first call, instead of a fresh list. The fix is the standard Python idiom: default to None, and create the real list inside the function body.

def collect_path(grid: list[list[int]], row: int, col: int, path: list[tuple[int, int]] | None = None) -> list[tuple[int, int]]:
    if path is None:
        path = []
    path.append((row, col))
    if col + 1 < len(grid[0]):
        collect_path(grid, row, col + 1, path)
    return path

grid = [[0, 0, 0]]
print(collect_path(grid, 0, 0))
print(collect_path(grid, 0, 0))

Output:

[(0, 0), (0, 1), (0, 2)]
[(0, 0), (0, 1), (0, 2)]

Both calls now produce the identical, correct path, because each call gets its own fresh list rather than reusing state left behind by the previous call.

Best Practices

• Represent movement as a small list of (delta_row, delta_col) tuples instead of four separate if-blocks — it makes switching between 4-directional and 8-directional (adding diagonals) a one-line change.
• Always bound-check with 0 <= next_row < rows and 0 <= next_col < cols, in that exact form — skipping the lower bound lets Python’s negative-index wraparound silently read the wrong cell instead of erroring.
• In BFS, mark a cell visited at the moment you enqueue it, not when you dequeue it, to avoid enqueuing duplicates.
• Use collections.deque for BFS queues, never a plain list with pop(0) — list.pop(0) is O(n), which silently turns an O(rows × cols) BFS into something far slower.
• For DFS on large grids, prefer an explicit stack over recursion; Python’s default recursion limit (around 1000) can be hit by a long, snake-like path through a large grid.
• Use a separate visited set or boolean grid instead of mutating the input matrix to mark cells, unless the problem explicitly allows (or asks for) in-place marking.
• Reach for spiral, diagonal, or boundary traversal only when the problem asks for a specific visiting order; for \”touch every cell once\” tasks, plain nested loops are simpler and equally O(rows × cols).

Practice Exercises

• Rotate Image. Given an n × n matrix, rotate it 90 degrees clockwise in place. Hint: transpose the matrix (swap matrix[row][col] with matrix[col][row]), then reverse each row. For input [[1, 2], [3, 4]], the expected result is [[3, 1], [4, 2]].
• Diagonal Traversal. Given a matrix, return its elements visited diagonally in a zig-zag (up-right, then down-left, alternating). Try it on [[1, 2, 3], [4, 5, 6], [7, 8, 9]] and check your output against a friend’s or an online judge before assuming it’s right.
• Max Area of Island. Extend the num_islands BFS from Example 3 so that instead of counting islands, it returns the size (cell count) of the largest island. Hint: have bfs return the number of cells it visited, and track the maximum across all calls.

Summary

• Row-major traversal is the default: two nested loops, O(rows × cols) time, O(1) extra space.
• Spiral and boundary traversal use four shrinking boundaries (top, bottom, left, right) instead of a fixed loop, but still visit each cell once: O(rows × cols) time, O(rows × cols) space for the output.
• Grid BFS/DFS treats the matrix as an implicit graph, generating neighbors from a small directions list; each cell is visited once, giving O(rows × cols) time and space.
• Always bound-check with both a lower and upper bound — Python’s negative-index wraparound will not raise an error for you.
• Mark BFS cells visited at enqueue time, not dequeue time, to avoid duplicate work.
• Never use a mutable default argument (like path=[]) in a recursive accumulator — default to None and initialize inside the function.