123. Rotate a Square Matrix Clockwise

Why this mechanism works

Clockwise rotation maps (r,c) to (c,n-1-r). Decompose that mapping into a transpose, which produces (c,r), followed by reversing each row, which changes its column to n-1-r. Swap only one triangular half during transposition so pairs are not undone.

State and boundaries

After transposition, row r holds original column r. Row reversal then establishes the final clockwise coordinate mapping.

Protocol

1. Swap matrix[r][c] with matrix[c][r] only for c>r.
2. Reverse each row in place.
3. Return the matrix.

Visualization

1 2 3       7 4 1
4 5 6  ->   8 5 2
7 8 9       9 6 3

Python implementation

def rotate_clockwise(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()
    return matrix

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 rotate_clockwise: n = len(matrix)
matrix=[[1, 2, 3], [4, 5, 6], [7, 8, 9]]; n=3

L3 rotate_clockwise: for r in range(n):
matrix=[[1, 2, 3], [4, 5, 6], [7, 8, 9]]; n=3; r=0

L4 rotate_clockwise: for c in range(r + 1, n):
matrix=[[1, 2, 3], [4, 5, 6], [7, 8, 9]]; n=3; r=0; c=1

L5 rotate_clockwise: matrix[r][c], matrix[c][r] = matrix[c][r], matrix[r][c]
matrix=[[1, 4, 3], [2, 5, 6], [7, 8, 9]]; n=3; r=0; c=1

L4 rotate_clockwise: for c in range(r + 1, n):
matrix=[[1, 4, 3], [2, 5, 6], [7, 8, 9]]; n=3; r=0; c=2

L5 rotate_clockwise: matrix[r][c], matrix[c][r] = matrix[c][r], matrix[r][c]
matrix=[[1, 4, 7], [2, 5, 6], [3, 8, 9]]; n=3; r=0; c=2

L3 rotate_clockwise: for r in range(n):
matrix=[[1, 4, 7], [2, 5, 6], [3, 8, 9]]; n=3; r=1; c=2

L5 rotate_clockwise: matrix[r][c], matrix[c][r] = matrix[c][r], matrix[r][c]
matrix=[[1, 4, 7], [2, 5, 8], [3, 6, 9]]; n=3; r=1; c=2

... 3 intermediate state changes omitted ...

L6 rotate_clockwise: for row in matrix:
matrix=[[7, 4, 1], [2, 5, 8], [3, 6, 9]]; n=3; r=2; c=2; row=[2, 5, 8]

L7 rotate_clockwise: row.reverse()
matrix=[[7, 4, 1], [8, 5, 2], [3, 6, 9]]; n=3; r=2; c=2; row=[8, 5, 2]

L6 rotate_clockwise: for row in matrix:
matrix=[[7, 4, 1], [8, 5, 2], [3, 6, 9]]; n=3; r=2; c=2; row=[3, 6, 9]

L7 rotate_clockwise: row.reverse()
matrix=[[7, 4, 1], [8, 5, 2], [9, 6, 3]]; n=3; r=2; c=2; row=[9, 6, 3]

L2 rotate_clockwise: n = len(matrix)
matrix=[]; n=0

Why the solution is correct

Each off-diagonal pair is exchanged once and diagonal cells stay fixed, giving a transpose. Reversing row positions transforms each copied coordinate (c,r) into (c,n-1-r), exactly the clockwise rotation formula.

Time and space

O(n^2) time and O(1) auxiliary space.

Common mistakes

Swapping both triangular halves undoes the transpose. Reversing columns rather than rows after transposition rotates in the other direction.

Reasoning card

Transfer exercise

Derive counterclockwise and 180-degree rotations by composing reflections, and test four clockwise rotations as an identity.