Generated by Codex with GPT-5

Quick facts

• Difficulty: MEDIUM
• Problem: Rotate Image
• Main tags: Array, Math, Matrix

What the problem is really asking

The input is an n x n matrix, and the task is to rotate it 90 degrees clockwise.

The important constraint is that the rotation must happen in place. That means the matrix itself must be rearranged without allocating another full n x n matrix for the final answer.

So this is really an index-mapping problem: every cell must move to its rotated position, and the challenge is to do that cleanly without losing values along the way.

The key idea

The easiest way to derive the solution is to briefly allow the “wrong” idea first.

If extra space were allowed, the mapping is straightforward:

matrix[row][column] should move to matrix[column][n - 1 - row]

That formula tells exactly where every value goes after a clockwise rotation.

The real interview step is noticing that this mapping can be decomposed into two simple in-place operations:

1. transpose the matrix across the main diagonal
2. reverse every row

After transposing, a value at (row, column) moves to (column, row). After reversing that row, it moves to (column, n - 1 - row).

That is exactly the target position for a clockwise rotation.

Why this works so well

Transposition is easy to do in place because each swap only involves two mirrored positions across the diagonal.

Reversing each row is also easy to do in place because each row can be reversed with a standard two-pointer swap.

Together, those two operations touch every element a constant number of times, so the total cost is:

• Time: O(n^2)
• Extra space: O(1)

That is the optimal interview answer because every cell must be moved at least once, so O(n^2) time is unavoidable.

How to derive it in an interview

A clean way to talk through it is:

First, imagine building a second matrix. That reveals the rotated index mapping immediately. Then ask whether that mapping can be broken into simpler in-place transformations. Once transposition is recognized, the remaining mismatch is only that each row is still backwards for a clockwise rotation. Reversing each row finishes the job.

This explanation usually lands better than jumping straight to code because it shows the reasoning, not just the trick.

Best approach

The transpose-then-reverse method is the best default solution:

• it is fully in place
• it is easy to explain and verify
• it matches the optimal O(n^2) time and O(1) extra-space bounds

There is another optimal in-place method that rotates one square layer at a time with four-way swaps. That also works, but it is harder to reason about and easier to get wrong under interview pressure.

Python solution

The implementation should do exactly two things:

First, swap across the main diagonal so rows become columns. Then reverse each row so the transposed matrix becomes a clockwise rotation.

That keeps the code short, but more importantly, it keeps the logic obvious. If an interviewer asks why it works, the index mapping explains it directly.

Interview follow-ups

Could you solve it by rotating one layer at a time?

Yes. Another in-place solution treats the matrix like concentric square rings. For each ring, it rotates four corresponding cells at a time: top takes left, right takes top, bottom takes right, and left takes bottom. This also runs in O(n^2) time and O(1) extra space because every value still moves only a constant number of times. The tradeoff is clarity. The layer-based method is more mechanical and usually more error-prone because the boundary math is trickier.

How would you rotate the matrix 90 degrees counterclockwise instead?

The same decomposition idea still works. For a counterclockwise rotation, one clean approach is to transpose first and then reverse each column. Another equally good approach is to reverse the order of the rows first and then transpose. Both work because they produce the counterclockwise index mapping instead of the clockwise one. The complexity stays the same at O(n^2) time and O(1) extra space.

What if using another matrix were allowed?

Then the simplest solution is to allocate a second n x n matrix and write each value directly into its rotated destination using the mapping (row, column) -> (column, n - 1 - row). That version is often the easiest one to invent from scratch, and it is still O(n^2) time. The tradeoff is the extra O(n^2) space, which violates the in-place constraint of the original problem.

Why does the in-place trick depend on the matrix being square?

A true m x n rectangular matrix rotated 90 degrees becomes an n x m matrix, so its shape changes. That means an in-place rotation is no longer just a permutation of positions inside the same fixed grid. In practice, that is why this problem specifically uses an n x n matrix. The square shape lets the algorithm reorder values within the same storage layout.

Production-level Python code

from typing import List


Matrix = List[List[int]]


def transpose_in_place(square_matrix: Matrix) -> None:
    """Swap values across the main diagonal."""
    matrix_size = len(square_matrix)

    for row_index in range(matrix_size):
        for column_index in range(row_index + 1, matrix_size):
            square_matrix[row_index][column_index], square_matrix[column_index][row_index] = (
                square_matrix[column_index][row_index],
                square_matrix[row_index][column_index],
            )


def reverse_each_row_in_place(square_matrix: Matrix) -> None:
    """Reverse each row so the transposed matrix becomes a clockwise rotation."""
    for row in square_matrix:
        row.reverse()


def rotate_clockwise_in_place(square_matrix: Matrix) -> None:
    """
    Rotate an n x n matrix 90 degrees clockwise in place.

    A clockwise rotation can be decomposed into:
    1. transpose
    2. reverse each row
    """
    transpose_in_place(square_matrix)
    reverse_each_row_in_place(square_matrix)


class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Modify matrix in place. LeetCode expects no return value.
        """
        rotate_clockwise_in_place(matrix)