DSAPrep
MediumMath & Geometry

Rotate Image

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.

Example 1

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

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]]

Constraints

  • n == matrix.length == matrix[i].length
  • 1 <= n <= 20
  • -1000 <= matrix[i][j] <= 1000
View original on LeetCode ↗

Rotating clockwise sends the cell at (r, c) to (c, n-1-r). Building a fresh matrix with that formula is easy but costs O(n²) extra space. The in-place trick decomposes the rotation into two simpler, well-understood operations: transpose (flip across the main diagonal, which turns rows into columns) followed by reversing each row (which flips left-right) — together those two steps land every element exactly where the rotation formula says it should go.

Extra Matrix

Time O(n²)Space O(n²)

Allocate a new n x n matrix. For every source cell (r, c), write it directly to its rotated destination (c, n-1-r), then copy the new matrix back over the original (the problem’s in-place requirement is only there to push you toward the optimal solution — this version still runs correctly, just not for free).

class Solution:
    def rotate(self, matrix: list[list[int]]) -> None:
        n = len(matrix)
        rotated = [[0] * n for _ in range(n)]
        for r in range(n):
            for c in range(n):
                rotated[c][n - 1 - r] = matrix[r][c]
        matrix[:] = rotated

Correctness: the destination formula (c, n-1-r) is exactly the definition of a 90° clockwise rotation, so every cell lands in the right place in one pass. Complexity: every cell is visited once → O(n²) time, but a whole second matrix is kept alive at the same time as the original → O(n²) space.

Transpose + Reverse Rows

OptimalTime O(n²)Space O(1)

Transpose the matrix in place by swapping matrix[r][c] with matrix[c][r] for every pair above the diagonal (each pair is swapped exactly once, so nothing gets overwritten before it is used). Then reverse each row. Composing the two: transposing sends (r, c) → (c, r), and reversing row c sends column index r to n-1-r, so the final position is (c, n-1-r) — the same destination as the rotation formula, achieved with only a constant number of temporary variables.

class Solution:
    def rotate(self, matrix: list[list[int]]) -> None:
        n = len(matrix)
        for r in range(n):
            for c in range(r + 1, n):
                matrix[r][c], matrix[c][r] = matrix[c][r], matrix[r][c]
        for row in matrix:
            row.reverse()

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

1
2
3
4
5
6
7
8
9
1 / 7
comparingresultcurrent

Transpose step: swap (0,1) and (1,0) -> 2 and 4 trade places.

Complexity: the transpose touches roughly n²/2 pairs and the row reversals touch every cell once more → O(n²) time, but only a few scalar temporaries are used → O(1) extra space.