~/techniques/matrices

Matrices in place

Rotate, spiral through and mark a grid without a second copy. Each trick starts with a formula for where cell (r, c) goes.

what

Work out where each cell (r, c) must end up, then get it there with swaps or markers so no value is lost on the way.

use when

A grid must change in place, be read in an unusual order, or a number is stored digit by digit.

time

O(rows·cols)

space

O(1) extra

You’ll recognise it when

The input is a grid and the task says in place, or O(1) extra space: rotate it, flip it, transpose it, mark it.
You must read a grid in an unusual order: a spiral, ring by ring, or along the diagonals.
A cell affects its whole row or column, but only based on the grid as it was at the start.
A number is stored as a list of digits or a string, often too long for a machine integer, and you must add, multiply or reverse it.

If the task is to find paths or connected regions in a grid, you want BFS or DFS instead. This page is about moving values around, not exploring.

Picture a full bookshelf that you must put in a new order, with no spare shelf. You can’t lift every book off first. You can swap two books at a time, and you need to know where each book belongs before you start.

A grid in place is the same. First write down where the value at (r, c) must go as a formula. Then find moves that get every value there without overwriting one you still need. Swaps are safe because nothing is lost. A few cells you have finished with can also serve as scratch space.

The formulas are short. For an n × n grid:

Move	the value at `(r, c)` goes to
Transpose (mirror across the diagonal)	`(c, r)`
Flip left to right	`(r, n - 1 - c)`
Flip upside down	`(n - 1 - r, c)`
Quarter turn clockwise	`(c, n - 1 - r)`
Quarter turn anticlockwise	`(n - 1 - c, r)`

Two more come up all the time:

Flat index. A grid with cols columns stored row by row puts (r, c) at i = r * cols + c. Going back, r, c = divmod(i, cols). Use the number of columns, not rows.
Layers. The rings of a grid, from the outside in. Cell (r, c) is in layer min(r, c, rows - 1 - r, cols - 1 - c). An n × n grid has (n + 1) // 2 layers, and the last one is a single cell when n is odd.

How it works

We’ll turn an n × n grid a quarter turn clockwise, in place. The quarter turn is exactly a transpose followed by a left-to-right flip, and both of those are just swaps.

Scroll through the steps and the graphic follows along. You can also press play, step with the arrow keys, or edit the grid: try an odd size, where the middle cell never moves.

The value at (r, c) must end up at (c, n - 1 - r). Writing it there straight away would overwrite a value you haven’t moved yet.
Round one is the transpose. Visit every cell above the diagonal, where c > r.
Swap it with its mirror, (c, r). Cells on the diagonal stay where they are. Each pair is swapped exactly once, which is why c starts at r + 1.
After the transpose, row r holds what column r held, from top to bottom. The turned grid needs it from bottom to top.
Round two: reverse each row.
Loop c over the left half of the row, c < n // 2. In an odd-sized grid the middle cell stays put.
Swap (r, c) with its partner (r, n - 1 - c). Once a row is reversed, it matches the turned grid.
Both rounds are done and every value is in place, with no second grid.

loading matrices…

Why it’s correct: the transpose sends (r, c) to (c, r). The row reversal then sends that to (c, n - 1 - r), which is exactly where the quarter turn wants it. Each round only swaps pairs, and each pair only once, so no value is ever lost or moved twice.

def rotate(grid):
    """Turn an n x n grid 90 degrees clockwise, in place."""
    n = len(grid)
    # 1. Transpose: swap each cell above the diagonal with its mirror.
    for r in range(n):
        for c in range(r + 1, n):
            grid[r][c], grid[c][r] = grid[c][r], grid[r][c]
    # 2. Reverse each row: swap each cell in the left half with its partner.
    for r in range(n):
        for c in range(n // 2):
            grid[r][c], grid[r][n - 1 - c] = grid[r][n - 1 - c], grid[r][c]

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

// Turn an n x n grid 90 degrees clockwise, in place.
void rotate(vector<vector<int>>& grid) {
    int n = grid.size();
    // 1. Transpose: swap each cell above the diagonal with its mirror.
    for (int r = 0; r < n; r++)
        for (int c = r + 1; c < n; c++)
            swap(grid[r][c], grid[c][r]);
    // 2. Reverse each row: swap each cell in the left half with its partner.
    for (int r = 0; r < n; r++)
        for (int c = 0; c < n / 2; c++)
            swap(grid[r][c], grid[r][n - 1 - c]);
}

class Rotate {
    // Turn an n x n grid 90 degrees clockwise, in place.
    static void rotate(int[][] grid) {
        int n = grid.length;
        // 1. Transpose: swap each cell above the diagonal with its mirror.
        for (int r = 0; r < n; r++) {
            for (int c = r + 1; c < n; c++) {
                int t = grid[r][c];
                grid[r][c] = grid[c][r];
                grid[c][r] = t;
            }
        }
        // 2. Reverse each row: swap each cell in the left half with its partner.
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n / 2; c++) {
                int t = grid[r][c];
                grid[r][c] = grid[r][n - 1 - c];
                grid[r][n - 1 - c] = t;
            }
        }
    }
}

Four-way swaps, one layer at a time

The other classic way turns each ring separately. In a quarter turn, four cells trade places in a cycle: top goes to right, right to bottom, bottom to left and left to top. Save one of the four, then shift the other three along.

def rotate_layers(grid):
    n = len(grid)
    for layer in range(n // 2):
        first, last = layer, n - 1 - layer
        for i in range(first, last):
            off = i - first
            top = grid[first][i]
            grid[first][i] = grid[last - off][first]            # left to top
            grid[last - off][first] = grid[last][last - off]    # bottom to left
            grid[last][last - off] = grid[i][last]              # right to bottom
            grid[i][last] = top                                 # top to right

It touches each cell once instead of twice, but the index arithmetic is easy to get wrong under pressure. Transpose and reverse is shorter and easier to check. Know both, and use the one you can write without bugs.

Walking in a spiral

To read a grid in a clockwise spiral, keep four boundaries: top, bottom, left and right. Read along the top row, then move top down one. Read down the right column, then move right in one. Do the same for the bottom row and the left column, and repeat while top <= bottom and left <= right.

The catch is the last layer. It can be a single row or a single column. Once you have read it left to right, you must not read it back right to left. So check the boundaries again before the bottom row and the left column.

def spiral_order(grid):
    """Every value of an m x n grid, read in a clockwise spiral."""
    out = []
    top, bottom = 0, len(grid) - 1
    left, right = 0, len(grid[0]) - 1
    while top <= bottom and left <= right:
        for c in range(left, right + 1):           # top row, left to right
            out.append(grid[top][c])
        top += 1
        for r in range(top, bottom + 1):           # right column, downwards
            out.append(grid[r][right])
        right -= 1
        if top <= bottom:                          # a row is still left
            for c in range(right, left - 1, -1):   # bottom row, right to left
                out.append(grid[bottom][c])
            bottom -= 1
        if left <= right:                          # a column is still left
            for r in range(bottom, top - 1, -1):   # left column, upwards
                out.append(grid[r][left])
            left += 1
    return out

#include <vector>
using namespace std;

// Every value of an m x n grid, read in a clockwise spiral.
vector<int> spiralOrder(const vector<vector<int>>& grid) {
    vector<int> out;
    int top = 0, bottom = grid.size() - 1;
    int left = 0, right = grid[0].size() - 1;
    while (top <= bottom && left <= right) {
        for (int c = left; c <= right; c++) out.push_back(grid[top][c]);      // top row
        top++;
        for (int r = top; r <= bottom; r++) out.push_back(grid[r][right]);    // right column
        right--;
        if (top <= bottom) {                                                  // a row is still left
            for (int c = right; c >= left; c--) out.push_back(grid[bottom][c]);   // bottom row
            bottom--;
        }
        if (left <= right) {                                                  // a column is still left
            for (int r = bottom; r >= top; r--) out.push_back(grid[r][left]);     // left column
            left++;
        }
    }
    return out;
}

class Spiral {
    // Every value of an m x n grid, read in a clockwise spiral.
    static int[] spiralOrder(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[] out = new int[m * n];
        int k = 0;
        int top = 0, bottom = m - 1, left = 0, right = n - 1;
        while (top <= bottom && left <= right) {
            for (int c = left; c <= right; c++) out[k++] = grid[top][c];      // top row
            top++;
            for (int r = top; r <= bottom; r++) out[k++] = grid[r][right];    // right column
            right--;
            if (top <= bottom) {                                              // a row is still left
                for (int c = right; c >= left; c--) out[k++] = grid[bottom][c];   // bottom row
                bottom--;
            }
            if (left <= right) {                                              // a column is still left
                for (int r = bottom; r >= top; r--) out[k++] = grid[r][left];     // left column
                left++;
            }
        }
        return out;
    }
}

The first row and column as markers

Here is the task: wherever a cell is 0, set its whole row and column to 0. Only zeros present at the start count. If you clear rows as you find zeros, the new zeros look like old ones and spread across the whole grid. So you need to mark first, then clear.

Two extra lists, one flag per row and one per column, work in O(rows + cols) space. To get O(1), store those flags in the grid itself. Cell (r, 0) flags row r, and cell (0, c) flags column c. Row 0 and column 0 then hold flags instead of their own data. So record in two booleans whether they held a zero at the start, and clear them last.

def set_zeroes(grid):
    """Wherever a cell is 0, set its whole row and column to 0, in place."""
    m, n = len(grid), len(grid[0])
    # Row 0 and column 0 are about to become markers, so first note
    # whether they hold a zero of their own.
    first_row_zero = any(grid[0][c] == 0 for c in range(n))
    first_col_zero = any(grid[r][0] == 0 for r in range(m))
    # Mark: a zero at (r, c) flags row r in column 0 and column c in row 0.
    for r in range(1, m):
        for c in range(1, n):
            if grid[r][c] == 0:
                grid[r][0] = 0
                grid[0][c] = 0
    # Clear every inner cell whose row or column is flagged.
    for r in range(1, m):
        for c in range(1, n):
            if grid[r][0] == 0 or grid[0][c] == 0:
                grid[r][c] = 0
    # Clear the marker row and column last, from the two flags.
    if first_row_zero:
        for c in range(n):
            grid[0][c] = 0
    if first_col_zero:
        for r in range(m):
            grid[r][0] = 0

#include <vector>
using namespace std;

// Wherever a cell is 0, set its whole row and column to 0, in place.
void setZeroes(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    // Row 0 and column 0 are about to become markers, so first note
    // whether they hold a zero of their own.
    bool firstRowZero = false, firstColZero = false;
    for (int c = 0; c < n; c++) if (grid[0][c] == 0) firstRowZero = true;
    for (int r = 0; r < m; r++) if (grid[r][0] == 0) firstColZero = true;
    // Mark: a zero at (r, c) flags row r in column 0 and column c in row 0.
    for (int r = 1; r < m; r++)
        for (int c = 1; c < n; c++)
            if (grid[r][c] == 0) grid[r][0] = grid[0][c] = 0;
    // Clear every inner cell whose row or column is flagged.
    for (int r = 1; r < m; r++)
        for (int c = 1; c < n; c++)
            if (grid[r][0] == 0 || grid[0][c] == 0) grid[r][c] = 0;
    // Clear the marker row and column last, from the two flags.
    if (firstRowZero) for (int c = 0; c < n; c++) grid[0][c] = 0;
    if (firstColZero) for (int r = 0; r < m; r++) grid[r][0] = 0;
}

class SetZeroes {
    // Wherever a cell is 0, set its whole row and column to 0, in place.
    static void setZeroes(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        // Row 0 and column 0 are about to become markers, so first note
        // whether they hold a zero of their own.
        boolean firstRowZero = false, firstColZero = false;
        for (int c = 0; c < n; c++) if (grid[0][c] == 0) firstRowZero = true;
        for (int r = 0; r < m; r++) if (grid[r][0] == 0) firstColZero = true;
        // Mark: a zero at (r, c) flags row r in column 0 and column c in row 0.
        for (int r = 1; r < m; r++)
            for (int c = 1; c < n; c++)
                if (grid[r][c] == 0) grid[r][0] = grid[0][c] = 0;
        // Clear every inner cell whose row or column is flagged.
        for (int r = 1; r < m; r++)
            for (int c = 1; c < n; c++)
                if (grid[r][0] == 0 || grid[0][c] == 0) grid[r][c] = 0;
        // Clear the marker row and column last, from the two flags.
        if (firstRowZero) for (int c = 0; c < n; c++) grid[0][c] = 0;
        if (firstColZero) for (int r = 0; r < m; r++) grid[r][0] = 0;
    }
}

Digits stored in an array

Some numbers are too long for a machine integer, so they arrive as a list of digits or a string. Work the way you would on paper: start from the last digit and carry into the next one.

def add_digits(a, b):
    """a and b hold whole numbers as digit lists, most significant digit first."""
    out, carry = [], 0
    i, j = len(a) - 1, len(b) - 1
    while i >= 0 or j >= 0 or carry:
        s = carry + (a[i] if i >= 0 else 0) + (b[j] if j >= 0 else 0)
        out.append(s % 10)
        carry = s // 10
        i -= 1
        j -= 1
    return out[::-1]    # built from the last digit, so turn it round

Adding one is add_digits(digits, [1]). The answer only grows by a digit when every digit was 9. Some related rules:

Multiplying. Digit i of a times digit j of b (both counted from the left) lands at position i + j + 1 of a result with len(a) + len(b) slots. Add up every product first, then sweep the carries from right to left and strip leading zeros.
Taking a number apart. x % 10 is the last digit and x // 10 drops it. In C++ and Java, check that result * 10 + d fits before you compute it, not after it has overflowed.
Letter labels such as A to Z, then AA, work like base 26 with digits 1 to 26 instead of 0 to 25. Subtract one before each remainder.

Why it’s O(n²)

An n × n grid has n² cells, and every method here does a fixed amount of work per cell. The transpose makes n(n - 1) / 2 swaps and the row reversal makes n · ⌊n / 2⌋, so fewer than n² swaps in all. You can’t do better, because every cell except the centre has to move.

Task	Time	Extra space
Quarter turn, either method	O(n²)	O(1)
Spiral order	O(rows·cols)	O(1) besides the output
Mark zeros with two lists	O(rows·cols)	O(rows + cols)
Mark zeros in row 0 and column 0	O(rows·cols)	O(1)
Add two digit lists	O(len(a) + len(b))	O(1) besides the output
Multiply two digit lists	O(len(a) · len(b))	O(len(a) + len(b))

Common mistakes

Swapping every pair twice in the transpose

If c runs over the whole row, each pair is swapped once from each side, and the second swap undoes the first. The grid ends up unchanged.

for c in range(n):          # ✗ (0, 1) swaps with (1, 0), then back again
for c in range(r + 1, n):   # ✓ only cells above the diagonal

Reading the last row or column twice in a spiral

When the middle of the grid is a single row, the top-row pass reads it and moves top past bottom. Without a fresh check, the bottom-row pass reads it again backwards.

for c in range(right, left - 1, -1):   # ✗ runs even when top > bottom
if top <= bottom:                      # ✓ only if a row is still left

Clearing while you scan

Setting a row and column to zero as soon as you see a zero creates new zeros. Cells you reach later can’t tell them from the zeros that were there at the start, so the clearing spreads.

if grid[r][c] == 0: clear(r, c)                  # ✗ new zeros spread further
if grid[r][c] == 0: grid[r][0] = grid[0][c] = 0  # ✓ mark now, clear later

Forgetting the last carry

A carry out of the first digit needs a new digit in front. Without it, 99 + 1 comes out as 00.

while i >= 0 or j >= 0:             # ✗ drops the final carry
while i >= 0 or j >= 0 or carry:    # ✓ one more round writes the 1

Variations

Anticlockwise turn. Transpose, then reverse each column. Or reverse each row first, then transpose.
Half turn. Reverse the order of the rows, then reverse each row: (r, c) goes to (n - 1 - r, n - 1 - c).
Turning a non-square grid. An rows × cols grid becomes cols × rows, so it can’t stay in the same array. Build a new one with new[r][c] = old[rows - 1 - c][r].
Updating every cell at once. When each cell’s new value depends on its neighbours’ old values, store both in the cell, for example 2 for “was 1, becomes 0”. Decode everything in a second pass.
Numbers that repeat. If you keep transforming a number (say, summing the squares of its digits), the values must eventually repeat. Spot the cycle with a set, or with fast and slow pointers.

Check yourself

5 quick questions. Pick an answer to see why it's right or wrong.

1
You must turn an n × n grid a quarter turn anticlockwise, in place. Which pair of steps does it?
Anticlockwise sends (r, c) to (n - 1 - c, r). The transpose gives (c, r), and reversing each column flips the row index to n - 1 - c. Transpose then reverse each row is the clockwise turn. Reversing rows and columns is a half turn. A copy works, but it uses O(n²) extra space, so it isn’t in place.
2
A 3 × 4 grid holds 0 to 11 row by row. The code wants the cell at flat index 7. What does it print?
```
rows, cols = 3, 4
flat = list(range(rows * cols))
grid = [flat[r * cols:(r + 1) * cols] for r in range(rows)]
r, c = divmod(7, rows)
print(grid[r][c])
```
A flat index counts whole rows, so you divide by the number of columns: divmod(7, 4) is (1, 3), which holds 7. Dividing by the rows gives (2, 1), a real cell but the wrong one, which holds 9. No error is raised, so this bug is easy to miss on square grids, where both give the same answer.
3
Transpose then reverse each row. How many swaps is that for a 4 × 4 and a 5 × 5 grid?
```
def swaps(n):
    count = 0
    for r in range(n):
        for c in range(r + 1, n):
            count += 1
    for r in range(n):
        for c in range(n // 2):
            count += 1
    return count
print(swaps(4), swaps(5))
```
The transpose swaps each pair above the diagonal once: n(n - 1) / 2, so 6 and 10. The reversal swaps n // 2 pairs in each of the n rows: 8 and 10. That’s 14 and 20, fewer than n² swaps, which is why the whole turn is O(n²) with O(1) extra space. 6 and 10 counts only the transpose.
4
To clear every row and column that holds a zero in O(1) extra space, you use row 0 and column 0 as flags. Why do you also need two separate booleans?
Once grid[0][c] means “clear column c”, you can no longer tell whether row 0 had a zero of its own. The two booleans remember that, and row 0 and column 0 are cleared last, after every flag has been read. The speed comes from marking, not from the booleans.

This spiral leaves out the if top <= bottom and if left <= right checks before the bottom row and the left column. On which grid does it return the wrong order?

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

Practice problems

Solve these right here, in Python, C++ or Java. Tests run as you go.

All 9 problems on this topic