Problem Statement

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Additional information

• n == matrix.length == matrix[i].length
• 1 <= n <= 20
• -1000 <= matrix[i][j] <= 1000

Example 1:

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

Explanation: The 3x3 matrix is rotated 90 degrees clockwise. The first column [1, 4, 7] becomes the first row [7, 4, 1] (reversed).

Example 2:

Input: matrix = [[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]]

Explanation: The 4x4 matrix is rotated 90 degrees clockwise in-place.

Transpose and Reverse

Intuition

The most elegant way to rotate a matrix 90 degrees clockwise is to perform two simple matrix operations in sequence:

1. Transpose: Swap elements across the main diagonal (top-left to bottom-right). matrix[i][j] becomes matrix[j][i].
2. Reverse Rows: Reverse each row of the transposed matrix.

Why this works:

• Transpose: Converts rows into columns. The first row becomes the first column.
• Reverse: The first column (which was the first row) needs to be the last column for a 90-degree clockwise rotation. Reversing the rows achieves this.

Algorithm

Step 1: Iterate through the matrix to transpose it.

• Loop i from 0 to n.
• Loop j from i + 1 to n (only visit the upper triangle to avoid swapping twice).
• Swap matrix[i][j] with matrix[j][i].

Step 2: Iterate through the matrix rows to reverse them.

• For each row in the matrix, reverse it in-place (e.g., row.reverse()).

Step 3: Return the matrix (for the purpose of validation, although the operation is in-place).

def rotate(matrix: list[list[int]]) -> list[list[int]]:
    n = len(matrix)
    
    # 1. Transpose (swap rows and columns)
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
            
    # 2. Reverse each row
    for row in matrix:
        row.reverse()
        
    return matrix

Time & Space Complexity

• Time Complexity: O(n^2). We process each cell in the grid twice (once for transpose, once for reverse).
• Space Complexity: O(1). We modify the matrix in-place without using extra space for another matrix.