Matrix Traversal

At a glance

The instinct

When the input is a grid and the question is about order or shape rather than connectivity, you are in matrix-traversal land. Spiral printing, rotating a picture, zeroing rows, validating a Sudoku board, or stepping a cellular automaton all boil down to the same skill: turning a 2D movement rule into clean row/column arithmetic without falling off the edge.

The key mental switch is to stop thinking "nested for loop" and start thinking "where are my walls, which way am I facing, and what do I already know about this cell?"

Recognise it

Not this pattern if...

• The question asks about connected regions, islands or shortest paths - that is BFS/DFS on a grid (graph pattern).
• Each cell's answer is built from neighbours' answers (min path sum, unique paths) - that is 2D dynamic programming.
• Rows and columns are sorted and you are searching for a value - that is a staircase search or binary search.

Memory hack

Analogy: a matrix is a chessboard and you are a piece with a fixed move set. Direction arrays are your move set; boundaries are the edge of the board; marker cells are notes you scribble on squares you have already finished with.

Say it out loud in the interview:

1. "My state is: current cell, current direction, and the four boundaries (or a visited marker)."
2. "My move rule is: step, and if I'd leave bounds or hit a visited cell, turn clockwise."
3. "My edge cases are: one row, one column, 1x1, and non-square inputs."

How it works

Most problems in this family reduce to one of three moves:

1. Boundary shrinking (Spiral Matrix): keep top, bottom, left, right. Sweep the top row, then the right column, then (if rows remain) the bottom row, then (if columns remain) the left column; tighten the matching fence after each sweep.
2. Geometric decomposition (Rotate Image): a clockwise 90-degree turn equals transpose (a[i][j] <-> a[j][i]) followed by reversing every row. Counter-clockwise: transpose then reverse every column.
3. In-place markers (Set Matrix Zeroes, Game of Life): reuse storage you are allowed to overwrite. Use row 0 and column 0 as flag arrays, or encode "was alive, now dead" as an extra state like 2 or a second bit.

flowchart TD
    A["Start: top=0, bottom=m-1, left=0, right=n-1"] --> B[Sweep top row left to right, top++]
    B --> C[Sweep right column top to bottom, right--]
    C --> D{"top ≤ bottom?"}
    D -- yes --> E[Sweep bottom row right to left, bottom--]
    D -- no --> F
    E --> F{"left ≤ right?"}
    F -- yes --> G[Sweep left column bottom to top, left++]
    F -- no --> H
    G --> H{"top ≤ bottom and left ≤ right?"}
    H -- yes --> B
    H -- no --> I[Done]

The two guard checks are the whole trick: on a single remaining row or column, they stop you from walking the same cells back the other way.

Java template

import java.util.*;

class MatrixTraversal {
    // Template 1: boundary-shrinking spiral walk.
    static List<Integer> spiral(int[][] a) {
        List<Integer> out = new ArrayList<>();
        if (a.length == 0) return out;
        int top = 0, bottom = a.length - 1, left = 0, right = a[0].length - 1;
        while (top <= bottom && left <= right) {
            for (int c = left; c <= right; c++) out.add(a[top][c]);
            top++;
            for (int r = top; r <= bottom; r++) out.add(a[r][right]);
            right--;
            if (top <= bottom) {
                for (int c = right; c >= left; c--) out.add(a[bottom][c]);
                bottom--;
            }
            if (left <= right) {
                for (int r = bottom; r >= top; r--) out.add(a[r][left]);
                left++;
            }
        }
        return out;
    }

    // Template 2: neighbour scan with direction vectors (4 or 8 directions).
    static final int[] DR = {-1, -1, -1, 0, 0, 1, 1, 1};
    static final int[] DC = {-1, 0, 1, -1, 1, -1, 0, 1};

    static int countNeighbours(int[][] a, int r, int c) {
        int m = a.length, n = a[0].length, count = 0;
        for (int d = 0; d < 8; d++) {
            int nr = r + DR[d], nc = c + DC[d];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
            if ((a[nr][nc] & 1) == 1) count++; // read the OLD state from bit 0
        }
        return count;
    }

    // Template 3: rotate n x n clockwise in place = transpose + reverse rows.
    static void rotate(int[][] a) {
        int n = a.length;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++) {
                int t = a[i][j]; a[i][j] = a[j][i]; a[j][i] = t;
            }
        for (int[] row : a)
            for (int l = 0, r = n - 1; l < r; l++, r--) {
                int t = row[l]; row[l] = row[r]; row[r] = t;
            }
    }
}

Complexity

Every cell is touched a constant number of times, so you cannot beat O(m·n) - the win is always in space.

Variations

• Spiral generation - fill 1..n² in spiral order instead of reading it (Spiral Matrix II). Same fences, write instead of read.
• Layer rotation - rotate ring by ring with a four-way swap; also used for "rotate by k" on a ring.
• Marker reuse - store flags in the first row/column, as in Set Matrix Zeroes; remember a separate boolean for column 0 itself.
• Simultaneous update - encode old and new state in one int (bit 0 = now, bit 1 = next), as in Game of Life.
• Bucketing by derived id - box index (r / 3) * 3 + c / 3, as in Valid Sudoku.
• Diagonal walks - group by r + c and flip direction on alternate diagonals (Diagonal Traverse).

Common mistakes

• Mixing up m (rows, a.length) and n (columns, a[0].length) on rectangular input.
• In Set Matrix Zeroes, zeroing row 0 / column 0 too early and erasing the flags you still need - process them last.
• In Game of Life, updating cells in place without encoding the old state, so later neighbours read new values.
• Transposing with j starting at 0 instead of i + 1, which swaps every pair twice and undoes the work.
• Not checking for an empty matrix (a.length == 0) before touching a[0].

All practice problems

5 problems on this site use this pattern, easiest first. Solve them in order and say the instinct out loud before you code.