Rotate Image

Rotate Image asks you to turn a square matrix a quarter-turn clockwise — and to do it in place, without allocating a second grid. The elegant trick is to express one rotation as two passes you already know: a transpose and a row reversal.

The slow way first

The obvious idea is to build a fresh n x n matrix and copy each element to its rotated position: the value at (r, c) lands at (c, n-1-r). That works and is easy to reason about, but it uses O(n²) extra space — and the problem explicitly forbids a second matrix.

The question to ask: can I reach the same final layout by rearranging the values I already have? It turns out a 90° clockwise rotation is exactly a transpose followed by reversing each row — two in-place passes, no extra grid.

The idea: transpose, then reverse each row

First transpose the matrix: swap every a[i][j] with a[j][i]. This reflects the grid across its main diagonal, so rows become columns. Then reverse each row left-to-right. The combination of those two reflections is a 90° clockwise turn.

The key insight: to transpose without double-swapping, only walk the cells above the diagonal (j starts at i + 1). The diagonal itself never moves.

Walk through it

Step through the animation. In phase one, three diagonal pairs swap — (0,1)↔(1,0), (0,2)↔(2,0), (1,2)↔(2,1) — and the center cell 5 stays put. In phase two, each row swaps its end values inward: 1 4 7 becomes 7 4 1, and so on. After both passes the grid reads 7 4 1 / 8 5 2 / 9 6 3 — the original turned a quarter-turn clockwise.

Pseudocode

n = number of rows
# pass 1: transpose across the main diagonal
for i from 0 to n-1:
    for j from i+1 to n-1:
        swap a[i][j] and a[j][i]
# pass 2: reverse each row
for each row in a:
    reverse the row in place

The Python solution

def rotate(matrix):
    n = len(matrix)
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    for row in matrix:
        row.reverse()
    return matrix

• n = len(matrix) is the side length of the square grid.
• The double loop transposes: j starts at i + 1, so we only touch cells above the diagonal and swap each with its mirror below.
• Line 5 is the transpose swap — Python lets us exchange two values in one tuple assignment.
• The second loop reverses each row in place with row.reverse(), which is O(n) per row and uses no extra array.
• Everything mutates matrix directly, so the extra space is O(1).

Complexity

Both approaches touch every cell, so the time is O(n²) — unavoidable, since the answer has n² entries. The win here is space: we rotate using only a handful of swaps and never allocate a second grid.

When this pattern shows up

Practice