Matrix manipulation

Problem

A matrix problem asks you to move values around a grid, or to read them in an unusual order, usually without a second grid. The naive answer copies everything into a fresh matrix, which costs O(rows · cols) memory and is often explicitly forbidden ("rotate in place", "use constant space"). The pattern is to find a formula for where cell (r, c) goes, then split that move into steps simple enough to do with swaps.

Intuition

Rotating by 90 degrees clockwise sends row r to column n − 1 − r. Doing that in one move needs a four-way swap, which is easy to get wrong. Two reflections give the same result: reflect across the main diagonal (the transpose, row r becomes column r), then reflect left to right (column r becomes column n − 1 − r). Each reflection only swaps pairs of cells, so each is a short loop. This is the matrix version of rotating an array with three reversals: a hard move written as a few easy ones.

The top row 1 2 3 4 becomes the left column after the transpose and the right column after the reversal. The diagram scrolls sideways on a narrow screen.

A spiral is the same idea applied to reading order. Keep four numbers, top, bottom, left and right, for the rows and columns not yet read. Read the top row and move top down; read the right column and move right left; and so on. The unread part is always a rectangle, so each side is a plain loop between two bounds.

Mechanics

Rotation as two reflections

The transpose swaps (i, j) with (j, i) for every j > i, so each pair is swapped exactly once and the diagonal stays put: n(n − 1)/2 swaps. Reversing a row swaps (r, c) with (r, n − 1 − c). Composing them, (r, c) goes to (c, r) and then to (c, n − 1 − r), which is exactly where a clockwise turn sends it. For counter-clockwise, reverse each row first and then transpose, or transpose and reverse the order of the rows. A half turn is reversing the order of the rows and then each row.

Rotation by layers

The direct method walks the matrix in concentric square layers. In each layer, the cell on the top edge, its partner on the right edge, the one on the bottom edge and the one on the left edge form a cycle of four, and a clockwise rotation moves each value one step around that cycle. Saving the top value in a temporary and shifting the other three into place does the cycle with one extra variable. A 4 × 4 matrix has 4 such cycles: 3 in the outer layer and 1 in the inner one. It moves each value exactly once, but the index arithmetic is easy to get wrong, which is why the two-reflection version is the usual interview answer.

Spiral boundaries

Invariant: the cells not yet output are exactly the rectangle top..bottom × left..right. Each side outputs one edge of that rectangle and moves the matching bound inward, so the invariant holds after every side. The loop runs while the rectangle is non-empty. The two checks in the middle of the loop matter for rectangles that are one row tall or one column wide: after the top row and the right column, the rectangle may already be empty, and without the checks the bottom row or left column would be read a second time, backwards.

Each colour is one side. After the fourth side only the middle row's 6 and 7 are left, and a fifth side, a top row again, reads them.

Markers in the first row and column

Set Matrix Zeroes needs to know which rows and which columns contain a zero, which is O(rows + cols) extra memory if you keep two boolean arrays. The trick stores those arrays inside the matrix: cell (r, 0) marks row r and cell (0, c) marks column c. Any row or column that gets a marker is going to be zeroed anyway, so writing a 0 into it destroys nothing that matters. Two details keep it correct. First, the first row and column are themselves rows and columns that might need clearing, so read whether they contain a zero into two variables before writing any markers. Second, clear them last, after the interior has been cleared from the markers, or the cleared first row would mark every column.

Non-square matrices

The transpose of an r × c matrix is c × r, so it cannot be done in place with simple swaps; build a new one. In Python [list(col) for col in zip(*matrix)] is the idiom: zip takes the i-th item of every row, which is column i. Rotation in place only makes sense for square matrices, which is why Rotate Image promises one.

Worked example

Rotate. The 4 × 4 matrix above, one stage per row of the table:

The layer method moves the same values through 4 cycles of four. The first is (0, 0) → (0, 3) → (3, 3) → (3, 0): the corners 1, 4, 16, 13 each move one corner clockwise.

Spiral. The 3 × 4 matrix above. Bounds are (top, bottom, left, right) after each side:

After the last side, top (2) is past bottom (1), so the rectangle is empty and the loop ends with all 12 values read.

Set zeroes. The matrix has zeros at (1, 1) and (2, 0). The first row has no zero and the first column contains zero, so only the column flag is set.

The zero at (1, 1) writes markers into (1, 0) and (0, 1). The zero at (2, 0) is already its own row marker. Clearing the interior from the markers zeroes rows 1 and 2 and column 1, and the column flag finally zeroes column 0. Row 0 keeps its 3 and 4 because the first-row flag is false.

Transpose. The 2 × 3 matrix [1, 2, 3], [4, 5, 6] becomes the 3 × 2 matrix [1, 4], [2, 5], [3, 6].

Implementation

def rotate(matrix):
    n = len(matrix)
    for i in range(n):
        for j in range(i + 1, n):              # j > i: swap each pair once
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    for row in matrix:
        row.reverse()

Variations and edge cases

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


def set_zeroes(matrix):
    rows, cols = len(matrix), len(matrix[0])
    first_row = 0 in matrix[0]
    first_col = any(matrix[r][0] == 0 for r in range(rows))
    for r in range(1, rows):
        for c in range(1, cols):
            if matrix[r][c] == 0:
                matrix[r][0] = matrix[0][c] = 0
    for r in range(1, rows):
        for c in range(1, cols):
            if matrix[r][0] == 0 or matrix[0][c] == 0:
                matrix[r][c] = 0
    if first_row:
        for c in range(cols):
            matrix[0][c] = 0
    if first_col:
        for r in range(rows):
            matrix[r][0] = 0


def rotate_by_layers(matrix):
    n = len(matrix)
    for layer in range(n // 2):
        last = n - 1 - layer
        for k in range(last - layer):
            saved = matrix[layer][layer + k]
            matrix[layer][layer + k] = matrix[last - k][layer]
            matrix[last - k][layer] = matrix[last][last - k]
            matrix[last][last - k] = matrix[layer + k][last]
            matrix[layer + k][last] = saved


def transpose(matrix):
    return [list(col) for col in zip(*matrix)]

• Transpose loop bounds. Starting j at 0 instead of i + 1 swaps every pair twice and leaves the matrix unchanged.
• Single row or column. A 1 × n or n × 1 spiral is where the mid-loop checks earn their place; test both shapes.
• Marker order. Compute first_row and first_col before any marker is written, and apply them after the interior is cleared.
• Reading what you just wrote. In-place updates that depend on neighbours, as in Game of Life, need the old value too: encode both states in the cell (for example with extra bits or values 2 and 3) and decode in a second pass.
• Spiral Matrix II. Generating a spiral uses the same four bounds, writing an increasing counter instead of reading values.

Complexity and tradeoffs

• Brute-force baseline: build a second matrix. Rotate by writing m[i][j] into new[j][n - 1 - i], walk the spiral with a visited grid, or read zeroes from a copy while clearing the original. Each is already O(rows · cols) time; what the in-place versions save is the O(rows · cols) extra memory, which is usually what the problem asks for.
• Rotate: O(n²) time and O(1) extra space either way. Two reflections touch each cell about twice; the layer method moves each once but is harder to write correctly.
• Spiral: O(rows · cols) time; O(1) beyond the output. A visited grid plus a direction vector also works but costs O(rows · cols) memory.
• Set zeroes: O(rows · cols) time; O(1) extra with markers, O(rows + cols) with two sets, which is simpler and fine unless the problem demands constant space.
• Transpose: O(rows · cols) time and space for a new matrix; in-place transposition of a non-square matrix exists (following permutation cycles) but is never worth it in an interview.
• When it is the wrong tool. If the grid is a maze of cells connected to their neighbours, you want grid graph search. If the question is about sums of sub-rectangles, use 2D prefix sums, and for best paths across a grid, grid DP.

Problems

Transpose Matrix is the warm-up for the zip(*matrix) idiom. Rotate Image, Spiral Matrix and Set Matrix Zeroes are the three core moves of this page and appear on every list; solve Rotate Image both ways and Set Matrix Zeroes first with two sets, then with markers.

Easy

• 867. Transpose Matrix NeetCode 250
  The transposed matrix's cell (i, j) is the original's (j, i), and its shape is the original's flipped.

Medium

• 48. Rotate Image Blind 75 Grind 169 NeetCode 150 NeetCode 250
  A clockwise turn is a transpose followed by reversing each row, and both steps can be done in place.
• 54. Spiral Matrix Blind 75 Grind 169 NeetCode 150 NeetCode 250
  Keep four boundaries and peel the matrix one ring at a time, shrinking a boundary after each side is walked.
• 73. Set Matrix Zeroes Blind 75 Grind 169 NeetCode 150 NeetCode 250
  Use the first row and column as marker storage, remembering separately whether they themselves must be zeroed.

Also uses this pattern

These problems have a different home page, but this idea is part of their solution.

• 304. Range Sum Query 2D - Immutable Medium
• 2392. Build a Matrix With Conditions Hard

Connections

Rotation by reflections is the two-dimensional version of the reversal tricks in in-place array tricks, and the first-row markers are the same "reuse the input as scratch space" idea as marking seen values by negating them. Grids also show up as graphs in grid graphs and as tables in grid DP; this page is the case where the grid is just data to rearrange.

Check yourself

References

• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, 3rd edition, chapter 28 on matrix operations and the appendix on matrices (D.1), for transposes and index notation.
• Skiena, S., The Algorithm Design Manual, the catalog's numerical problems chapter, under matrix multiplication and related operations.
• Sedgewick and Wayne, Algorithms, section 1.1 on two-dimensional arrays.
• Cate, E. G. and Twigg, D. W., "Algorithm 513: Analysis of in-situ transposition", ACM Transactions on Mathematical Software, 1977, on transposing a non-square matrix in place by following permutation cycles.
• The NeetCode roadmap and the Blind 75, Grind 169, NeetCode 150 and NeetCode 250 lists, used as the index of topics and problems.