DSAMotivator

Rotate Image

Medium·📐 Math & Geometry·Open on LeetCode ↗

Turn a square matrix 90 degrees clockwise, modifying it in place rather than building a new one.

a 3 × 3 matrixstep 1/9
2
7
1
9
4
6
3
8
5

A clockwise rotation is a transpose, then a reversal of every row.

1def rotate(matrix):
2    n = len(matrix)
3    for r in range(n):
4        for c in range(r + 1, n):
5            matrix[r][c], matrix[c][r] = matrix[c][r], matrix[r][c]
6    for row in matrix:
7        row.reverse()
Read the 9 steps as text
  1. 1A clockwise rotation is a transpose, then a reversal of every row.
  2. 2Reflect across the diagonal: (0, 1) and (1, 0) trade places.
  3. 3Reflect across the diagonal: (0, 2) and (2, 0) trade places.
  4. 4Reflect across the diagonal: (1, 2) and (2, 1) trade places.
  5. 5Transposed. The first column is now the first row — but upside down.
  6. 6Reverse row 0 and it lands the right way round.
  7. 7Reverse row 1 and it lands the right way round.
  8. 8Reverse row 2 and it lands the right way round.
  9. 9Two simple passes, and the matrix has turned 90° clockwise.

Start with the obvious solution

Allocate a second n×n matrix and copy each cell to its rotated position, then hand that back.

O(n²) time, O(n²) extra space

Why that isn't enough: The time is already optimal — every cell has to move. The problem is the copy: the question asks for an in-place rotation, and the extra grid is the one thing it forbids. Transpose-then-reverse achieves the same permutation using only swaps.

The idea

Rotating cell by cell means juggling four values at once around each ring, with index arithmetic that is very easy to get subtly wrong under interview pressure. It works, but it's the version you'll misremember.

There's a decomposition that removes all of that. A 90° clockwise rotation is a transpose — reflect across the main diagonal — followed by reversing each row. Two operations, each of which is trivially easy to write and check.

Why it's true is easier to see than to prove: transposing sends the first *column* to the first *row*, but in the wrong order — bottom-to-top instead of top-to-bottom. Reversing each row fixes exactly that.

The same trick generalises. Transpose then reverse each column gives you the counter-clockwise rotation, which is the natural follow-up question.

The approach

  1. 1Transpose: for every pair above the diagonal, swap matrix[r][c] with matrix[c][r].
  2. 2Only iterate c from r + 1 — walking the full square swaps every pair twice and lands you back where you started.
  3. 3Reverse each row in place.
  4. 4That's the rotation, with no second matrix allocated.

Complexity

Time
O(n²)
Space
O(1)

Every cell is touched a constant number of times, and there's nowhere near enough auxiliary storage to matter. O(n²) is optimal — you have to write every cell.

Code

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

What goes wrong

  • •Transposing over the whole matrix instead of the upper triangle. Each swap gets undone and the matrix comes out unchanged, which is a maddening bug to stare at.
  • •Reversing the columns instead of the rows, which produces the counter-clockwise rotation.
  • •Building a fresh matrix and returning it. Correct, but the problem asks for in place, and that constraint is the entire question.