Home / Blog / Matrix Traversal Interview Pattern

Matrix Traversal Interview Pattern

Published 2026-10-14 · Luna Interview

Grids show up everywhere in coding interviews: islands, mazes, game boards, images, spreadsheets. The good news is that almost all of them rely on the same small toolkit. This matrix traversal interview pattern guide covers how to classify a grid problem, the templates worth memorizing, and the off-by-one bugs that cost the most time.

First, classify the traversal

Ask yourself which of these the prompt needs:

1. Explore connected regions (islands, flood fill) → DFS or BFS
2. Shortest path in steps (maze, nearest exit) → BFS
3. Spread from many sources at once (rotting oranges, distance to nearest gate) → multi-source BFS
4. Visit in a fixed geometric order (spiral, diagonal, layer by layer) → boundary or index math
5. Transform in place (rotate, set zeroes) → index mapping with O(1) extra space
6. Path counts or best cost moving right/down → dynamic programming

Say it out loud:

"Since we need the minimum number of steps in an unweighted grid, BFS from the start guarantees the first time we reach the target is the shortest."

The direction array

Nearly every grid solution starts here:

DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]

def in_bounds(r, c, rows, cols):
    return 0 <= r < rows and 0 <= c < cols

For eight-directional movement, add the four diagonals. Mention which one the problem allows—it's a common clarifying question.

Template 1: DFS flood fill (count islands)

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

    def dfs(r, c):
        if not (0 <= r < rows and 0 <= c < cols) or grid[r][c] != '1':
            return
        grid[r][c] = '0'          # mark visited in place
        for dr, dc in DIRS:
            dfs(r + dr, c + dc)

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

Ask before mutating: "Is it OK to modify the input, or should I use a separate visited set?"

Also mention the recursion risk: a 1000×1000 grid of land can exceed the default recursion limit. An iterative stack or BFS avoids that.

Template 2: BFS shortest path

from collections import deque

def shortest_path(grid, start, target):
    rows, cols = len(grid), len(grid[0])
    q = deque([(start[0], start[1], 0)])
    seen = {start}
    while q:
        r, c, d = q.popleft()
        if (r, c) == target:
            return d
        for dr, dc in DIRS:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols \
               and grid[nr][nc] == 0 and (nr, nc) not in seen:
                seen.add((nr, nc))
                q.append((nr, nc, d + 1))
    return -1

Key habit: mark visited when you enqueue, not when you dequeue. Otherwise the same cell can be added many times.

Template 3: multi-source BFS

Put every source in the queue at distance 0, then run a normal BFS. Each layer represents one unit of time or distance.

"Instead of running BFS from each rotten orange separately, I'll start with all of them in the queue. That keeps it O(rows × cols) instead of multiplying by the number of sources."

Template 4: spiral order

Keep four boundaries and shrink them:

def spiral(m):
    res = []
    top, bottom, left, right = 0, len(m) - 1, 0, len(m[0]) - 1
    while top <= bottom and left <= right:
        for c in range(left, right + 1): res.append(m[top][c])
        top += 1
        for r in range(top, bottom + 1): res.append(m[r][right])
        right -= 1
        if top <= bottom:
            for c in range(right, left - 1, -1): res.append(m[bottom][c])
            bottom -= 1
        if left <= right:
            for r in range(bottom, top - 1, -1): res.append(m[r][left])
            left += 1
    return res

The two if checks prevent double-counting when a single row or column remains. Dry-run a 1×3 and a 3×1 matrix to prove it.

Template 5: diagonals and in-place transforms

• Diagonals: cells on the same diagonal share r - c; anti-diagonals share r + c. Group by that key.
• Rotate 90° clockwise in place: transpose (swap m[i][j] with m[j][i]), then reverse each row.
• Set matrix zeroes in O(1) space: use the first row and column as markers, with separate flags for whether they themselves contain a zero.

Decision table

Common bugs

1. Swapping rows and columns in bounds checks (len(grid) vs len(grid[0]))
2. Forgetting empty grids or empty rows
3. Marking visited on dequeue in BFS
4. Not restoring cells after backtracking in word search
5. Recursion depth on large grids
6. Using BFS when cells have different weights

Soft practice note

Grid problems reward a calm, repeatable routine: classify, pick the template, check bounds, dry-run a tiny case. If you want a structured way to practice that out loud with a timer, Luna Interview is built for rehearsal and prep—before the interview, not as a way around the rules during one.

Checklist

• [ ] Direction array and bounds helper on autopilot
• [ ] DFS flood fill and BFS shortest path from memory
• [ ] Multi-source BFS explained in one sentence
• [ ] Spiral boundaries dry-run on 1×N and N×1
• [ ] Rotate-in-place steps memorized
• [ ] Clarifying question: four or eight directions? Can I mutate input?

Once you see grids as graphs with free adjacency, most matrix problems become a choice between four or five templates.

Rehearse with an AI interview copilot, then browse commonly reported interview questions.