Matrix and Grid Traversal: Spiral, Rotate, Search & Code

A matrix is a grid of values in rows and columns: an image is a matrix of pixels, a map a matrix of land and water, a spreadsheet a matrix of cells. Matrix problems rarely need a clever algorithm. They need exact bookkeeping — which index is the row, where the edges are, which cells have been visited, and in what order to walk so that nothing is skipped or seen twice.

How a matrix is stored in memory

Memory is one long line, so C, C++, Java, Python and JavaScript all flatten a matrix in row-major order: row 0, then row 1, and so on. A Java int[][] or a list of lists is an outer array of separate rows, but each row is still laid out on its own, so neighbours in a row are neighbours in memory, and neighbours in a column are a whole row apart.

1. Memory is one long line, so the rows are laid end to end: row 0, then row 1, then row 2. The cell (2, 1) sits at offset 2 × 4 + 1 = 9, which holds 10. Read backwards, offset k is row k / cols and column k % cols.
2. Row by row, the loop reads memory in order: each step is to the very next address, so every block of memory the processor fetches is used in full before the next one is needed.
3. Column by column, every step jumps a whole row — 4 addresses here, thousands in a real image — so each fetched block yields one useful value. Same additions, several times slower on a large matrix: put the row loop outside.

That is why loop order matters: a processor fetches memory in blocks, so a row-by-row loop uses all of each block and a column-by-column loop one value of it. Put the row loop outside. The offset formula also runs backwards, which is how Search a 2D Matrix becomes an ordinary binary search on the flat index.

Indexing, bounds and the usual walks

Write every index as matrix[row][col] and name the sizes once: rows = matrix.length, cols = matrix[0].length. If a problem speaks of (x, y), x is usually the column, so translate once at the top. A cell is inside the grid when 0 <= r < rows and 0 <= c < cols.

Beyond row by row and column by column, the walks you need are the diagonals, and every diagonal has a number of its own.

Grouping cells by r - c solves Sort the Matrix Diagonally and Toeplitz Matrix. Matrix Diagonal Sum adds both diagonals and subtracts the centre once when n is odd.

Spiral order: four boundaries

Spiral Matrix asks for every element in clockwise spiral order. Keep four boundaries — top, bottom, left, right — around the part not yet visited:

• Walk the top row, the right column, the bottom row backwards and the left column upwards, moving each boundary inwards once its side is done.
• Stop when top > bottom or left > right.
• Before the bottom row and the left column, check that a row and a column are still left.

1. Four boundaries fence the part not visited yet — at first the whole matrix, shaded. Each side of the spiral walks one edge of that rectangle and then moves its boundary inwards, so the rectangle shrinks by one row or one column.
2. Top row, left to right: 1 2 3 4. That row is done, so top moves down (top 1, bottom 2, left 0, right 3).
3. Right column, downwards: 8 12. Then right moves in (top 1, bottom 2, left 0, right 2).
4. A row is still left (top ≤ bottom), so the bottom row is walked right to left: 11 10 9. Bottom moves up.
5. A column is still left, so the left column is walked upwards: 5. Left moves in (top 1, bottom 1, left 1, right 2).
6. Top row, left to right: 6 7. That row is done, so top moves down (top 2, bottom 1, left 1, right 2).
7. Right column, rows 2 to 1: an empty range, since top is past bottom — nothing is added, and right moves in anyway.
8. The check matters here: top (2) is past bottom (1), so no row is left. Walking the bottom row anyway would read row 1 again and add 6 a second time.
9. Left column, from row 1 up to row 2: empty again. Left moves in, and now left is past right too.
10. The rectangle is empty, so the loop stops. Every cell was visited exactly once, in spiral order: 1 2 3 4 8 12 11 10 9 5 6 7. O(rows × cols) time, and nothing but four integers of extra space.

Why it works. The boundaries keep an invariant: the cells not yet visited are exactly the rectangle from row top to bottom and column left to right. Each side walks one edge of that rectangle and then removes it, so every cell is visited once and the loop ends when the rectangle is empty. The checks exist because a rectangle with no rows left has no bottom row to walk.

The code

The program runs the matrix above and a single column, which needs the other check.

#include <iostream>
#include <vector>
using namespace std;

// Every element in clockwise spiral order, starting at the top-left corner.
vector<int> spiralOrder(const vector<vector<int>>& matrix) {
    vector<int> out;
    if (matrix.empty()) return out;
    int top = 0, bottom = (int)matrix.size() - 1;
    int left = 0, right = (int)matrix[0].size() - 1;
    // Invariant: the cells not visited yet are rows top..bottom, columns left..right.
    while (top <= bottom && left <= right) {
        for (int c = left; c <= right; c++) out.push_back(matrix[top][c]);    // top row
        top++;
        for (int r = top; r <= bottom; r++) out.push_back(matrix[r][right]);  // right column
        right--;
        if (top <= bottom) {  // a row is still left: the bottom one, backwards
            for (int c = right; c >= left; c--) out.push_back(matrix[bottom][c]);
            bottom--;
        }
        if (left <= right) {  // a column is still left: the left one, upwards
            for (int r = bottom; r >= top; r--) out.push_back(matrix[r][left]);
            left++;
        }
    }
    return out;
}

int main() {
    vector<vector<vector<int>>> inputs = {
        {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}},
        {{1}, {2}, {3}},
    };
    for (const vector<vector<int>>& matrix : inputs) {
        cout << matrix.size() << " x " << matrix[0].size() << " spiral:";
        for (int v : spiralOrder(matrix)) cout << " " << v;
        cout << "\n";
    }
    return 0;
}

import java.util.ArrayList;
import java.util.List;

public class Main {
    // Every element in clockwise spiral order, starting at the top-left corner.
    static List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> out = new ArrayList<>();
        if (matrix.length == 0) return out;
        int top = 0, bottom = matrix.length - 1;
        int left = 0, right = matrix[0].length - 1;
        // Invariant: the cells not visited yet are rows top..bottom, columns left..right.
        while (top <= bottom && left <= right) {
            for (int c = left; c <= right; c++) out.add(matrix[top][c]);    // top row
            top++;
            for (int r = top; r <= bottom; r++) out.add(matrix[r][right]);  // right column
            right--;
            if (top <= bottom) { // a row is still left: the bottom one, backwards
                for (int c = right; c >= left; c--) out.add(matrix[bottom][c]);
                bottom--;
            }
            if (left <= right) { // a column is still left: the left one, upwards
                for (int r = bottom; r >= top; r--) out.add(matrix[r][left]);
                left++;
            }
        }
        return out;
    }

    public static void main(String[] args) {
        int[][][] inputs = {
            {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}},
            {{1}, {2}, {3}},
        };
        for (int[][] matrix : inputs) {
            StringBuilder line = new StringBuilder(matrix.length + " x " + matrix[0].length + " spiral:");
            for (int v : spiralOrder(matrix)) line.append(" ").append(v);
            System.out.println(line);
        }
    }
}

def spiral_order(matrix):
    """Every element in clockwise spiral order, starting at the top-left corner."""
    out = []
    if not matrix:
        return out
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1
    # Invariant: the cells not visited yet are rows top..bottom, columns left..right.
    while top <= bottom and left <= right:
        for c in range(left, right + 1):  # top row
            out.append(matrix[top][c])
        top += 1
        for r in range(top, bottom + 1):  # right column
            out.append(matrix[r][right])
        right -= 1
        if top <= bottom:  # a row is still left: the bottom one, backwards
            for c in range(right, left - 1, -1):
                out.append(matrix[bottom][c])
            bottom -= 1
        if left <= right:  # a column is still left: the left one, upwards
            for r in range(bottom, top - 1, -1):
                out.append(matrix[r][left])
            left += 1
    return out


inputs = [
    [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]],
    [[1], [2], [3]],
]
for matrix in inputs:
    print(f"{len(matrix)} x {len(matrix[0])} spiral:", *spiral_order(matrix))

// Every element in clockwise spiral order, starting at the top-left corner.
function spiralOrder(matrix) {
  const out = [];
  if (matrix.length === 0) return out;
  let top = 0;
  let bottom = matrix.length - 1;
  let left = 0;
  let right = matrix[0].length - 1;
  // Invariant: the cells not visited yet are rows top..bottom, columns left..right.
  while (top <= bottom && left <= right) {
    for (let c = left; c <= right; c++) out.push(matrix[top][c]); // top row
    top++;
    for (let r = top; r <= bottom; r++) out.push(matrix[r][right]); // right column
    right--;
    if (top <= bottom) {
      // a row is still left: the bottom one, backwards
      for (let c = right; c >= left; c--) out.push(matrix[bottom][c]);
      bottom--;
    }
    if (left <= right) {
      // a column is still left: the left one, upwards
      for (let r = bottom; r >= top; r--) out.push(matrix[r][left]);
      left++;
    }
  }
  return out;
}

const inputs = [
  [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]],
  [[1], [2], [3]],
];
for (const matrix of inputs) {
  console.log(`${matrix.length} x ${matrix[0].length} spiral: ${spiralOrder(matrix).join(" ")}`);
}

3 x 4 spiral: 1 2 3 4 8 12 11 10 9 5 6 7
3 x 1 spiral: 1 2 3

The same boundaries write a spiral instead of reading one in Spiral Matrix II.

Rotating 90° in place: transpose, then reverse

Rotate Image asks for a quarter turn clockwise of an n × n matrix in place — a second matrix would cost another million values for a 1,000 × 1,000 image. Two passes of plain swaps do it:

1. Transpose: swap matrix[i][j] with matrix[j][i] for every j > i.
2. Reverse each row with two pointers.

1. A 90° clockwise turn sends the value at (i, j) to (j, 2 − i). Doing that directly needs cycles of four moves; it is simpler as two passes of plain swaps, a transpose and then a mirror of each row.
2. Transpose first: swap m[0][1] = 2 with m[1][0] = 4 across the main diagonal. The diagonal cells 1, 5 and 9 map to themselves and never move.
3. Swap m[0][2] = 3 with m[2][0] = 7 across the main diagonal. Only cells above the diagonal start a swap, so no pair is swapped back.
4. Swap m[1][2] = 6 with m[2][1] = 8 across the main diagonal. The transpose is done: row i now holds what column i held.
5. Now mirror each row. Row 0, [1, 4, 7], becomes [7, 4, 1]: its ends swap and the middle stays. Together with the transpose this moves (i, j) to (j, 2 − i), exactly the turn.
6. Row 1, [2, 5, 8], becomes [8, 5, 2]. Each row is mirrored on its own, so the rows can be done in any order.
7. Row 2, [3, 6, 9], becomes [9, 6, 3], the last swap: every value has reached its rotated place.
8. Rotated: [[7, 4, 1], [8, 5, 2], [9, 6, 3]]. The old first column 7, 4, 1, read bottom-up, is the new first row. Every cell is touched a constant number of times: O(n²) time and O(1) extra space.

Why transpose and reverse is a rotation

A quarter turn clockwise sends (i, j) to (j, n - 1 - i). The transpose sends (i, j) to (j, i), and reversing a row sends column c to n - 1 - c, so together they send (i, j) to (j, n - 1 - i) — the rotation, for every cell at once.

1. Follow two things: the top row (1, 2, 3, 4) and the value 7 at (1, 2). A quarter turn clockwise must send the top row to the right-hand column and (i, j) to (j, n − 1 − i).
2. Transpose: every value is mirrored across the main diagonal, so (i, j) goes to (j, i). The top row is now the left column, and 7 has moved to (2, 1). The diagonal itself never moves.
3. Reverse each row: column c goes to n − 1 − c, so (j, i) goes to (j, n − 1 − i). The left column swings to the right, and 7 lands at (2, 2).
4. (i, j) → (j, i) → (j, n − 1 − i) is exactly the quarter turn, for every cell at once: the top row is the right column read downwards. Two passes of swaps, O(n²) time and O(1) extra space.

The transpose loop must start j at i + 1, or each pair swaps twice and nothing changes; and only a square matrix transposes in place, which is why Transpose Matrix builds a new array. Anticlockwise is the same parts in the other order: reverse each row, then transpose.

#include <iostream>
#include <string>
#include <utility>
#include <vector>
using namespace std;

// Mirror across the main diagonal: (i, j) <-> (j, i). Only j > i, or each pair swaps back.
void transpose(vector<vector<int>>& m) {
    int n = (int)m.size();
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++) swap(m[i][j], m[j][i]);
}

// Reverse every row with two pointers: (r, c) <-> (r, n - 1 - c).
void reverseRows(vector<vector<int>>& m) {
    int n = (int)m.size();
    for (int r = 0; r < n; r++)
        for (int left = 0, right = n - 1; left < right; left++, right--) swap(m[r][left], m[r][right]);
}

void print(const string& label, const vector<vector<int>>& m) {
    cout << label << "\n";
    for (const vector<int>& row : m) {
        for (int c = 0; c < (int)row.size(); c++) cout << (c ? " " : "") << row[c];
        cout << "\n";
    }
}

int main() {
    vector<vector<int>> m = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
    print("Before:", m);
    transpose(m);    // (i, j) -> (j, i)
    print("Transposed:", m);
    reverseRows(m);  // (j, i) -> (j, n - 1 - i): a quarter turn clockwise
    print("Rotated:", m);
    return 0;
}

public class Main {
    // Mirror across the main diagonal: (i, j) <-> (j, i). Only j > i, or each pair swaps back.
    static void transpose(int[][] m) {
        int n = m.length;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++) {
                int t = m[i][j];
                m[i][j] = m[j][i];
                m[j][i] = t;
            }
    }

    // Reverse every row with two pointers: (r, c) <-> (r, n - 1 - c).
    static void reverseRows(int[][] m) {
        int n = m.length;
        for (int r = 0; r < n; r++)
            for (int left = 0, right = n - 1; left < right; left++, right--) {
                int t = m[r][left];
                m[r][left] = m[r][right];
                m[r][right] = t;
            }
    }

    static void print(String label, int[][] m) {
        System.out.println(label);
        for (int[] row : m) {
            StringBuilder line = new StringBuilder();
            for (int c = 0; c < row.length; c++) line.append(c > 0 ? " " : "").append(row[c]);
            System.out.println(line);
        }
    }

    public static void main(String[] args) {
        int[][] m = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        print("Before:", m);
        transpose(m);   // (i, j) -> (j, i)
        print("Transposed:", m);
        reverseRows(m); // (j, i) -> (j, n - 1 - i): a quarter turn clockwise
        print("Rotated:", m);
    }
}

def transpose(m):
    """Mirror across the main diagonal: (i, j) <-> (j, i). Only j > i, or each pair swaps back."""
    n = len(m)
    for i in range(n):
        for j in range(i + 1, n):
            m[i][j], m[j][i] = m[j][i], m[i][j]


def reverse_rows(m):
    """Reverse every row with two pointers: (r, c) <-> (r, n - 1 - c)."""
    n = len(m)
    for r in range(n):
        left, right = 0, n - 1
        while left < right:
            m[r][left], m[r][right] = m[r][right], m[r][left]
            left += 1
            right -= 1


def show(label, m):
    print(label)
    for row in m:
        print(*row)


m = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
show("Before:", m)
transpose(m)     # (i, j) -> (j, i)
show("Transposed:", m)
reverse_rows(m)  # (j, i) -> (j, n - 1 - i): a quarter turn clockwise
show("Rotated:", m)

// Mirror across the main diagonal: (i, j) <-> (j, i). Only j > i, or each pair swaps back.
function transpose(m) {
  const n = m.length;
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      [m[i][j], m[j][i]] = [m[j][i], m[i][j]];
    }
  }
}

// Reverse every row with two pointers: (r, c) <-> (r, n - 1 - c).
function reverseRows(m) {
  const n = m.length;
  for (let r = 0; r < n; r++) {
    for (let left = 0, right = n - 1; left < right; left++, right--) {
      [m[r][left], m[r][right]] = [m[r][right], m[r][left]];
    }
  }
}

function print(label, m) {
  console.log(label);
  for (const row of m) console.log(row.join(" "));
}

const m = [[1, 2, 3], [4, 5, 6], [7, 8, 9]];
print("Before:", m);
transpose(m); // (i, j) -> (j, i)
print("Transposed:", m);
reverseRows(m); // (j, i) -> (j, n - 1 - i): a quarter turn clockwise
print("Rotated:", m);

Before:
1 2 3
4 5 6
7 8 9
Transposed:
1 4 7
2 5 8
3 6 9
Rotated:
7 4 1
8 5 2
9 6 3

Set matrix zeroes with O(1) extra space

Set Matrix Zeroes: wherever there is a 0, set its whole row and column to 0. You must finish reading before you start writing. Two boolean arrays of marked rows and columns cost O(m + n); for O(1), the marks go into the matrix's own first row and column.

1. Wherever there is a 0, its whole row and column must become 0. There are two zeros here. The trap is to start writing zeros before you have finished finding them.
2. Zeroing while scanning: each new 0 is read later as if it were original and spreads its own row and column. 25 of 25 cells end up 0, and 9 of them (red) should have kept their value.
3. Row 0 and column 0 are about to become notepads, so first save whether they hold a 0 of their own: row 0 does not, column 0 does. Two booleans are all the extra space.
4. Scan the inner cells. Each 0 writes a mark — a 0 — at the start of its row and the top of its column (solid). Those cells were going to be zeroed anyway, so the marks destroy nothing. The 0 already in column 0 is its own row's mark.
5. Now read the marks: an inner cell becomes 0 when the start of its row or the top of its column holds a 0. Row 0 and column 0 are still untouched apart from the marks, which this step needs.
6. Last, the saved booleans: column 0 held a 0, so it is zeroed now and row 0 keeps its values. Doing this any earlier would have wiped the marks. O(rows × cols) time, O(1) extra space.

Each step's place is forced: the first row and column are saved before they become notepads, and they are zeroed last, because doing it earlier would wipe marks the inner pass still reads.

Searching a sorted matrix: the staircase walk

In Search a 2D Matrix II every row and column is sorted, but rows do not continue each other. Scanning is O(m × n) — a million comparisons for a 1,000 × 1,000 matrix. From the top-right corner one comparison discards a whole row or column, so the walk takes at most m + n steps: 2,000.

1. Every row is sorted left to right and every column top to bottom. Start at the top-right corner, 11: going left makes values smaller, going down makes them larger, so one comparison says which way to go.
2. 11 > 5, and everything below it in column 3 is larger still — none of it can be the target. The whole column is dropped and the walk moves left.
3. 7 > 5, and everything below it in column 2 is larger still — none of it can be the target. The whole column is dropped and the walk moves left.
4. 4 < 5, and everything to its left in row 0 is smaller still. The whole row is dropped and the walk moves down.
5. 5 equals the target: found at (1, 1) after 4 comparisons. Scanning every cell could have taken 16; the walk never takes more than rows + cols = 8.
6. Why not the top-left corner? From 1 both moves, right to 4 and down to 2, make the value larger, so a comparison cannot choose between them. The top-right or bottom-left corner is what makes one step drop a whole row or column.

Grid neighbours and direction arrays

Most grid problems step from a cell to the cells next to it. Rather than four hand-written if blocks, list the moves once as direction arrays and loop.

1. List the moves once: dr = [−1, 1, 0, 0] and dc = [0, 0, −1, 1]. Neighbour k of (r, c) is (r + dr[k], c + dc[k]) — one loop instead of four copied if-blocks, each a chance for a typo.
2. At the corner (0, 0), 2 of the four moves leave the grid. Test 0 ≤ nr < rows and 0 ≤ nc < cols before reading the cell — in Python a negative index silently reads the other end of the row instead of failing.
3. Problems that count diagonal neighbours too, such as Game of Life, add the four diagonal moves: eight pairs in the arrays, and the same loop and bounds check.

Game of Life uses all eight directions, and every cell must be updated from the old board: work from a copy, or keep both states in each cell with a bit manipulation trick.

A grid is a graph

Once you can list a cell's neighbours, a grid is a graph: each cell is a node, joined to the neighbours the problem lets you step to. Flood Fill is a depth-first search; Number of Islands counts the searches needed to cover the land; a shortest path through a grid is a breadth-first search. Mark each cell visited when you first reach it.

Time and space complexity

Reading every cell once is the floor; the gains come from not looking (the staircase) or not copying (rotation and zeroes in place).

How to recognise a matrix problem

• The input is a grid, board, image or m × n matrix.
• It asks for an order of visiting: spiral, diagonal, layer by layer.
• It says in place about a rotation or flip: look for a composition of swaps.
• Rows and columns are sorted: the staircase walk or a binary search.
• It says adjacent, connected, islands: a graph search over the grid.

Common mistakes

• Rows and columns swapped: test a non-square matrix.
• Transposing every pair: starting j at 0 swaps each pair back.
• Skipping the spiral checks: a middle row is printed twice.
• Writing while still reading: new values are read as old ones.
• Reading before the bounds check: Python's negative index reads the other end silently.
• Not marking visited cells: in Flood Fill, a new colour equal to the old one loops forever.

Practice in this order

1. Transpose Matrix: a result of a different shape.
2. Matrix Diagonal Sum: the two diagonals.
3. Flood Fill: direction arrays and a first grid search.
4. Spiral Matrix: four boundaries.
5. Rotate Image: transpose, then reverse.
6. Set Matrix Zeroes: markers in row 0 and column 0.
7. Search a 2D Matrix: one sorted list in disguise.
8. Search a 2D Matrix II: the staircase walk.
9. Game of Life: eight neighbours, updated at once.

The matrix problem list has every grid problem in the catalogue, from easy to hard. When these feel routine, the next stage is bit manipulation, and grids come back later as graphs.