Rotate Matrix 90 Degrees Clockwise

Problem

You are given an n × n 2D matrix representing an image. Your task is to rotate the entire matrix 90 degrees clockwise — and you must do it in place, using only O(1) extra space (not counting the input matrix itself).

This is a classic problem that tests your understanding of matrix transformations and your ability to manipulate 2D arrays without using additional data structures.

Input / Output Format

Input: A 2D list matrix of integers with dimensions n × n.

Output: The same matrix modified in place so that it is rotated 90 degrees clockwise. Return None — the mutation happens directly on the input.

Examples

Example 1

Input:  [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]

The first column (7,4,1) becomes the first row, and so on.

Example 2

Input:  [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

Example 3

Input:  [[1]]
Output: [[1]]

A 1×1 matrix is unchanged after rotation.

Approach Hints

There's a well-known two-step trick for rotating a matrix 90° clockwise in place:

1. Transpose the matrix: swap matrix[i][j] with matrix[j][i] for all i < j. After this step, rows become columns.
2. Reverse each row: reverse the elements in every row horizontally. After this step, the matrix is rotated 90° clockwise.

Why does this work? A 90° clockwise rotation maps element at (i, j) to position (j, n-1-i). The transpose maps (i, j) → (j, i), and reversing a row maps (j, i) → (j, n-1-i), combining to achieve the full rotation.

Complexity:

• Time: O(n²) — every element is touched a constant number of times.
• Space: O(1) — the operation is performed in place with no auxiliary arrays.

Function Signature

def rotate(matrix: list[list[int]]) -> None:
    # modify matrix in place
    pass