Algorithm

Rotate Image

Arrays & Strings Pattern

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.

CONSTRAINTS
  • 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]]
The top row [1,2,3] becomes the rightmost column, top to bottom. Each cell (i, j) landed at (j, n-1-i).
EXAMPLE 2
Input: matrix = [[1,2],[3,4]]
Output: [[3,1],[4,2]]
Smallest interesting case: transpose gives [[1,3],[2,4]], reversing rows gives [[3,1],[4,2]].
EXAMPLE 3
Input: matrix = [[1]]
Output: [[1]]
A 1×1 grid is unchanged by rotation — the loops simply do nothing.
Is the matrix always square?
Yes — n × n is guaranteed. That matters: a rectangular matrix cannot be rotated in place this way, since its dimensions change from m × n to n × m.
Must the rotation be in-place, or may I allocate a new matrix?
Strictly in-place. The statement explicitly forbids allocating another 2D matrix — O(1) extra space expected.
What about counter-clockwise, if asked as a follow-up?
Same decomposition, mirrored: transpose, then reverse each column (equivalently: reverse each row first, then transpose).

Rotating a matrix 90 degrees clockwise means shifting every element to its corresponding position in a new, turned orientation. The challenge is to perform this transformation in-place without using any extra grids or large temporary storage.

Extra Matrix Copy (O(N²) space)

The easiest way to rotate is to create a new empty matrix and map each cell to its new coordinates. If a cell is at (i, j), it will land at (j, n - 1 - i) in the rotated matrix.

python
n = len(matrix)
res = [[0] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        res[j][n - 1 - i] = matrix[i][j]
matrix[:] = res
2. The Insight: Grid Transposition & Reflection

Using a separate matrix takes O(N²) space. The core insight is that a 90° clockwise rotation is mathematically equivalent to two simple, in-place grid operations:
1. Transpose: Swap elements across the main diagonal (matrix[i][j] with matrix[j][i]).
2. Reverse Rows: Reverse each row horizontally.

Transpose and Flip (O(1) space)

We rotate the matrix in-place by performing these two steps:

python
n = len(matrix)

# 1. Transpose: Swap elements across diagonal
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 i in range(n):
    matrix[i].reverse()
Worked Example:3x3 Matrix
1
2
3
4
5
6
7
8
9
We start with our original 3x3 matrix in its initial orientation.
1
4
7
2
5
8
3
6
9
In our first step, we transpose the matrix by swapping elements across the main diagonal, turning rows into columns.
7
4
1
8
5
2
9
6
3
In our second step, we reverse each row horizontally to complete the clockwise 90-degree rotation of the matrix.
Interactive Strategy Visualization

Rotation Sequence

Transpose + Horizontal Reverse
1
2
3
4
5
6
7
8
9

Initial matrix. Goal: Rotate 90° clockwise in-place.

DIAGONAL SYMMETRY

Transposing swaps (i, j) with (j, i). This swaps the x and y axes, preparing the grid for its final rotated state.

MEMORY LIMITS

By performing these flips in-place, we use O(1) extra space. This is critical for large datasets like HD images.

O(N²) Time · O(N²) Copy
→
O(N²) Time · O(1) Transpose+Reverse