Rotate Image

Signal

"Rotate a grid in place, no extra matrix" is a geometric-transform problem — 90-degree rotation decomposes into two simpler in-place operations you already know: transpose, then reverse each row.

Approach

First transpose the matrix (swap matrix[i][j] with matrix[j][i] for every i < j), which flips it across the main diagonal. Then reverse each row. Composing those two operations is exactly a 90-degree clockwise rotation, and both steps are doable in place with O(1) extra space.

Skeleton

transpose(matrix)     # swap matrix[i][j] and matrix[j][i] for i < j only
for row in matrix:
    reverse(row)

Solution

def rotate(matrix: list[list[int]]) -> None:
    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()

Complexity

O(n²) time — every cell is touched a constant number of times. O(1) extra space — everything happens in place on the input matrix.

Pitfalls

• Transposing across all i, j instead of just i < j swaps every pair twice and undoes itself back to the original matrix.
• Reversing before transposing (or reversing columns instead of rows) produces a 90-degree counter-clockwise rotation instead — order and axis both matter.
• A direct per-cell formula (new[j][n-1-i] = old[i][j]) is also correct but needs either a full copy or careful 4-way cycle swapping to stay in place — transpose-then-reverse is easier to get right under pressure.