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.

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.