LeetCode 48: Rotate Image

Problem Restatement

We are given an n x n matrix representing an image.

We need to rotate the matrix by 90 degrees clockwise.

The rotation must be done in-place. That means we must modify the input matrix directly and must not allocate another matrix for the rotated result. The official problem states this in-place requirement directly.

Example:

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

After rotation:

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

Input and Output

Function shape:

def rotate(matrix: list[list[int]]) -> None:
    ...

First Thought: Use Another Matrix

A simple way is to create a new matrix.

For every original cell:

matrix[i][j]

its rotated position is:

matrix[j][n - 1 - i]

So we could copy values into a new matrix.

But the problem requires in-place rotation, so this approach violates the space requirement.

We need to rearrange the original matrix itself.

Key Insight

A 90 degree clockwise rotation can be done with two in-place operations:

1. Transpose the matrix.
2. Reverse each row.

Transpose means swapping across the main diagonal.

For example:

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

After transpose:

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

Then reverse each row:

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

This is the required clockwise rotation.

Algorithm

Let:

n = len(matrix)

First, transpose the matrix.

For every pair of indices where j > i, swap:

matrix[i][j], matrix[j][i]

Then reverse each row in-place.

For every row:

row.reverse()

The matrix is now rotated clockwise.

Walkthrough

Use:

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

First transpose.

Swap matrix[0][1] with matrix[1][0]:

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

Swap matrix[0][2] with matrix[2][0]:

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

Swap matrix[1][2] with matrix[2][1]:

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

Now reverse each row:

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

Correctness

Consider an original element at position (i, j).

After transposition, it moves to:

(j, i)

After reversing each row, the column index i becomes:

n - 1 - i

So the element moves from:

(i, j)

to:

(j, n - 1 - i)

That is exactly the position of (i, j) after a 90 degree clockwise rotation.

Since every element is moved according to the clockwise rotation rule, the final matrix is correct.

Complexity

Implementation

class Solution:
    def rotate(self, 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()

Code Explanation

We first compute the matrix size:

n = len(matrix)

Then we transpose the 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]

The inner loop starts at i + 1 so we only swap cells above the main diagonal.

This avoids swapping the same pair twice.

Then we reverse each row:

for row in matrix:
    row.reverse()

After these two operations, the matrix has been rotated 90 degrees clockwise in-place.

Testing

def run_tests():
    s = Solution()

    matrix = [
        [1, 2, 3],
        [4, 5, 6],
        [7, 8, 9],
    ]
    s.rotate(matrix)
    assert matrix == [
        [7, 4, 1],
        [8, 5, 2],
        [9, 6, 3],
    ]

    matrix = [
        [5, 1, 9, 11],
        [2, 4, 8, 10],
        [13, 3, 6, 7],
        [15, 14, 12, 16],
    ]
    s.rotate(matrix)
    assert matrix == [
        [15, 13, 2, 5],
        [14, 3, 4, 1],
        [12, 6, 8, 9],
        [16, 7, 10, 11],
    ]

    matrix = [[1]]
    s.rotate(matrix)
    assert matrix == [[1]]

    matrix = [
        [1, 2],
        [3, 4],
    ]
    s.rotate(matrix)
    assert matrix == [
        [3, 1],
        [4, 2],
    ]

    print("all tests passed")

run_tests()