TL;DR
Transpose then reverse each row (or a 4-way ring swap) rotates 90° clockwise in place — O(n²) time, O(1) extra space.
Approach 1 — Naive: copy into a fresh matrix
A clockwise 90° turn sends the cell at (i, j) to (j, n-1-i). The most direct way to express that is to build a new matrix and place each cell where it belongs.
from typing import List
def rotate(matrix: List[List[int]]) -> None:
n = len(matrix)
rotated = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n):
rotated[j][n - 1 - i] = matrix[i][j]
# copy back into the input so the mutation is in place
for i in range(n):
matrix[i] = rotated[i]
Complexity: O(n²) time, O(n²) extra space for rotated.
This is correct but violates the O(1)-space requirement, which is the point of the problem. The next two approaches rearrange the cells in place.
Approach 2 — Transpose, then reverse each row (in place)
The mapping (i, j) → (j, n-1-i) factors into two in-place moves. Transposing swaps (i, j) with (j, i), turning rows into columns. Reversing each row then flips the columns left-to-right, completing the clockwise turn. Both steps touch only the existing array, so no copy is needed.
from typing import List
def rotate(matrix: List[List[int]]) -> None:
n = len(matrix)
# transpose: swap across the main diagonal (j starts at i+1)
for i in range(n):
for j in range(i + 1, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
# reverse each row in place
for row in matrix:
row.reverse()
Walkthrough with [[1,2,3],[4,5,6],[7,8,9]]:
- Transpose (mirror across the diagonal):
[[1,4,7],[2,5,8],[3,6,9]].
- Reverse each row:
[[7,4,1],[8,5,2],[9,6,3]] — the required clockwise result.
Complexity: O(n²) time, O(1) extra space. This is the easiest approach to remember.
Approach 3 — 4-way cyclic ring swap (in place)
The matrix is a set of concentric rings, and a rotation cycles each ring’s four corresponding cells. For a top cell at (top, top + offset), its three partners are the right, bottom, and left cells at symmetric offsets. Rotate those four with a single temporary, walking offset around the ring.
from typing import List
def rotate(matrix: List[List[int]]) -> None:
n = len(matrix)
top, bottom = 0, n - 1
while top < bottom:
for offset in range(bottom - top):
tmp = matrix[top][top + offset]
# left -> top
matrix[top][top + offset] = matrix[bottom - offset][top]
# bottom -> left
matrix[bottom - offset][top] = matrix[bottom][bottom - offset]
# right -> bottom
matrix[bottom][bottom - offset] = matrix[top + offset][bottom]
# top -> right
matrix[top + offset][bottom] = tmp
top += 1
bottom -= 1
Walkthrough with [[1,2,3],[4,5,6],[7,8,9]] (outer ring, top=0, bottom=2):
offset = 0: the four corners 1 (top-left), 7 (bottom-left), 9 (bottom-right), 3 (top-right) cycle → 1 goes where 3 was, 3 where 9 was, 9 where 7 was, 7 where 1 was. Grid becomes [[7,2,1],[4,5,6],[9,8,3]].offset = 1: the four edge-midpoints 2, 4, 8, 6 cycle → [[7,4,1],[8,5,2],[9,6,3]].- Inner “ring” is just the center
5, untouched. Done.
Complexity: O(n²) time, O(1) extra space (one temporary). Same result in a single pass with no per-row reversal.
Common pitfalls
- In the transpose, starting
j at 0 instead of i + 1 swaps every pair twice and gives back the original matrix.
- Reassigning
matrix[i] = rotated[i] vs. mutating in place: because the function returns None, the caller keeps the original list object — rebind its rows or mutate contents, don’t just build a local.
- Rotating counter-clockwise by mistake: clockwise is transpose-then-reverse-rows; reverse-rows-then-transpose (or transpose-then-reverse-columns) gives the opposite direction.
- In the ring swap, mixing up the four index expressions — trace one ring on paper before trusting it.
Pattern takeaway
Grid transformations often decompose into a couple of in-place primitives (transpose, row or column reversal) whose composition equals the target motion. This is cheaper to reason about than a direct coordinate remap and uses no extra space. When a naive solution wants a second buffer, ask whether the same permutation can be realized by swapping cells that already exist.