Rotate a Matrix 90 Degrees In Place: Transpose, Then Reverse

Rotating a square image a quarter turn is trivial with a second grid: read each cell, write it where it belongs. The interview version forbids the second grid, and that is where people start drawing arrows on the whiteboard and getting lost in indices.

There is a way to avoid the arrows entirely: two simple reflections compose into a rotation. This article shows why, gives the ring-swap alternative, and checks both against the copy-based version.

The problem it solves

Given an n × n matrix, rotate it 90 degrees clockwise, modifying it in place with O(1) extra memory.

The same operation shows up in image processing, in board games that need to test a position under rotation, and in tile-matching puzzles. The in-place constraint matters when the grid is large or when the caller holds a reference to it and expects that object to change.

The intuition

Start from where each cell must go. In a clockwise quarter turn, row r becomes column n - 1 - r: the top row ends up on the right edge, read top to bottom. Formally, the cell at (r, c) moves to (c, n - 1 - r).

That mapping is two simpler ones glued together:

1. Transpose: (r, c) goes to (c, r). Mirror the grid across its main diagonal, so rows become columns.
2. Reverse each row: (c, r) goes to (c, n - 1 - r). Mirror left to right.

Apply both and (r, c) lands on (c, n - 1 - r) — exactly the rotation. Each step is easy to do in place. The transpose swaps each cell above the diagonal with its partner below, leaving the diagonal alone. Row reversal is two pointers walking inwards.

Counter-clockwise is the same idea with the other mirror: transpose, then reverse the order of the rows instead of each row's contents.

The alternative works directly on the mapping. Every cell belongs to a cycle of four: top goes to right, right to bottom, bottom to left, left to top. Walk the grid ring by ring from the outside in, and rotate each cycle of four with one temporary variable. It does a quarter of the writes but needs careful index arithmetic.

Watch it run

A 3 × 3 grid numbered 1 to 9. First the transpose: the diagonal 1, 5, 9 never moves, and three swaps exchange the cells across it. The result is close but mirrored — 1, 2, 3 run down the left column instead of the right. Then each row flips, and the grid reads 7 4 1 across the top: a quarter turn clockwise.

The code

Transpose-and-reverse in both directions, and the four-way ring rotation:

def rotate_clockwise(m):
    n = len(m)
    for r in range(n):
        for c in range(r + 1, n):               # upper triangle only
            m[r][c], m[c][r] = m[c][r], m[r][c] # mirror across the diagonal
    for row in m:
        row.reverse()                           # then flip left-right

def rotate_counter(m):
    n = len(m)
    for r in range(n):
        for c in range(r + 1, n):
            m[r][c], m[c][r] = m[c][r], m[r][c]
    m.reverse()                                 # flip top-bottom instead

def rotate_rings(m):                            # clockwise, four cells at a time
    n = len(m)
    for layer in range(n // 2):
        first, last = layer, n - 1 - layer
        for k in range(last - first):
            top = m[first][first + k]
            m[first][first + k] = m[last - k][first]        # left   -> top
            m[last - k][first] = m[last][last - k]          # bottom -> left
            m[last][last - k] = m[first + k][last]          # right  -> bottom
            m[first + k][last] = top                        # top    -> right

m = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
rotate_clockwise(m); print(m)       # [[7, 4, 1], [8, 5, 2], [9, 6, 3]]
rotate_counter(m); print(m)         # [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
rotate_rings(m); print(m)           # [[7, 4, 1], [8, 5, 2], [9, 6, 3]]

The ring version writes into the top from the left, the left from the bottom, and so on — backwards around the cycle — so each write lands on a cell whose value has already been saved.

All three are compared with the version nobody gets wrong: allocate a fresh grid and place m[r][c] at (c, n - 1 - r). The check also confirms that three clockwise turns equal one counter-clockwise turn:

import random

def rotated_copy(m):                    # brute force: new[c][n-1-r] = old[r][c]
    n = len(m)
    out = [[None] * n for _ in range(n)]
    for r in range(n):
        for c in range(n):
            out[c][n - 1 - r] = m[r][c]
    return out

random.seed(9)
ok = True
for _ in range(2000):
    n = random.randint(0, 7)
    m = [[random.randint(0, 9) for _ in range(n)] for _ in range(n)]
    want = rotated_copy(m)
    a = [row[:] for row in m]; rotate_clockwise(a)
    b = [row[:] for row in m]; rotate_rings(b)
    c = [row[:] for row in m]
    for _ in range(3):
        rotate_clockwise(c)             # three quarter turns clockwise...
    d = [row[:] for row in m]; rotate_counter(d)
    ok &= a == want == b and c == d     # ...equal one turn the other way
print(ok)                               # True

Sizes from 0 to 7 cover the empty grid, the single cell, and both odd and even sizes, where the centre either stays put or does not exist.

The complexity

Transpose touches each of the n × (n - 1) / 2 off-diagonal pairs once; the row reversals touch each cell once. That is O(n²) time — the size of the input, so no algorithm can do better. Extra memory is one temporary per swap: O(1). The ring version has the same bounds with fewer writes, since each cell is written exactly once.

Where it goes wrong

• Transposing the whole grid. If the inner loop runs c from 0 instead of r + 1, every pair is swapped twice and the grid ends where it started.
• Reversing the wrong thing. Reversing each row after a transpose gives clockwise; reversing the list of rows gives counter-clockwise. Mixing them up produces the other direction, which a grid that looks the same upside down will not catch.
• Non-square input. A 2 × 3 grid rotates into a 3 × 2 grid. That cannot happen inside the same rows, so the in-place version only applies to squares.
• Rebinding instead of mutating. In Python, the one-liner with zip builds a new grid. Assigned to the parameter name, it never reaches the caller:

def rotate_rebind(m):
    m = [list(row) for row in zip(*m[::-1])]    # builds a new grid, binds it locally

def rotate_slice(m):
    m[:] = [list(row) for row in zip(*m[::-1])] # writes into the caller's list

grid = [[1, 2], [3, 4]]
rotate_rebind(grid); print(grid)                # [[1, 2], [3, 4]]  -- unchanged
rotate_slice(grid); print(grid)                 # [[3, 1], [4, 2]]

The slice assignment fixes the visible bug, but it still allocates a full second grid, so it is not the O(1) memory answer.

For the grid indexing that this builds on, see grid traversal and neighbours.

How to say it in an interview

"A clockwise quarter turn sends (r, c) to (c, n - 1 - r). That's a transpose, (r, c) to (c, r), followed by reversing each row. Both are in place: the transpose swaps across the diagonal, visiting only the upper triangle, and each row reverses with two pointers. O(n²) time, O(1) space. For counter-clockwise I'd reverse the row order instead."

Then offer the ring rotation as the alternative that writes each cell once. Deriving the transpose-plus-reverse from the index mapping, rather than just asserting it, is what makes the answer convincing.