Rotate Image — Solution

Problem

Given an n×n grid of integers representing an image, rotate the entire grid 90 degrees clockwise — and you must do it in-place without allocating another matrix.

• Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
• Output: [[7,4,1],[8,5,2],[9,6,3]]
• Explanation: the first column of the original (7, 4, 1, bottom to top) becomes the first row of the result.

Counter-example: reversing the rows first then transposing gives a 90° counter-clockwise rotation — the order matters.

Intuition

A 90° clockwise rotation sends the element at row i, column j to row j, column n-1-i. Instead of computing that directly, notice that two simpler operations compose to exactly the same result: first transpose the matrix (flip across the main diagonal), then reverse each row. This lets you perform the entire rotation with standard in-place swaps.

Solution — Transpose + Reverse Rows

Swap the upper and lower triangles across the main diagonal to transpose, then flip each row left-to-right.

1. For each row i from 0 to n-1, iterate column j from i+1 to n-1 — this covers only the upper triangle so each pair is swapped exactly once.
2. Swap matrix[i][j] with matrix[j][i] to transpose.
3. After the full transpose, iterate over every row and reverse it in-place.
4. The matrix now holds the 90° clockwise rotation.

1class Solution:
2    def rotate(self, matrix: List[List[int]]) -> None:
3        n = len(matrix)
4
5        # transpose: iterate only the upper triangle so no pair is swapped twice
6        for i in range(n):
7            for j in range(i + 1, n):
8                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
9
10        # reversing each row turns the transpose into a clockwise rotation
11        for row in matrix:
12            row.reverse()

Time: O(n²) — every element is touched once during the transpose and once during the row reversal.
Space: O(1) — all swaps happen in-place with no auxiliary storage.

Complexity Summary

Common Mistakes

• Iterating the full square during the transpose — if j starts from 0 instead of i+1, each pair gets swapped twice and the matrix is returned to its original state.
• Reversing columns instead of rows — after transposing, a horizontal flip (reverse rows) completes clockwise rotation; reversing each column instead gives a counter-clockwise result.
• Swapping the two steps — reversing rows first then transposing rotates counter-clockwise; the order must be transpose then reverse.
• Trying to build the rotation formula directly without decomposing — computing destination indices (j, n-1-i) for each element during in-place swaps requires carefully cycling four elements at a time, which is correct but far harder to reason about than the two-step approach.
• Assuming this works for non-square matrices — the transpose operation requires equal dimensions; for rectangular matrices, transposing changes the shape and a different approach is needed.

Related Problems

• Spiral Matrix — traverses an n×m matrix by peeling off layers, requiring careful index tracking similar to in-place rotation
• Set Matrix Zeroes — in-place modification of a 2D matrix without extra space for the full matrix
• Game of Life — another in-place 2D grid transformation where the trick is encoding two states in one cell
• Rotate Array — applies the same reverse-based decomposition to rotate a 1D array in-place
• Search a 2D Matrix — builds intuition for how row and column indices map to linear positions in a matrix