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).

A matrix here is a square grid of numbers. Cell (i, j) means row i, column j, with rows counted top to bottom and columns left to right, both from 0. Before touching code, work out where each cell must go. Rotate the grid 90° clockwise and watch a whole row: the top row stands up and becomes the rightmost column (its first element on top). In general, row i lands in column n - 1 - i, and a cell's position along its row becomes its position down that column. So the mapping is: (i, j) moves to (j, n - 1 - i). Sanity-check a corner: the top-left (0, 0) moves to (0, n-1) — the top-right. Correct.

The easy version: with a second grid

With that mapping, rotation into a fresh matrix is one loop:

python
new_matrix = [[0] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        new_matrix[j][n - 1 - i] = matrix[i][j]
for i in range(n):
    matrix[i] = new_matrix[i][:]

The problem forbids exactly this — no second matrix. And in-place rotation is genuinely awkward if attacked directly: writing a value into its destination overwrites a value that has not moved yet. (Cells actually rotate in cycles of four: (i, j) displaces (j, n-1-i), which displaces the next, and the fourth loops back — doable, but the index bookkeeping is fiddly and error-prone under interview pressure.)

Two mirrors make a rotation

Here is the elegant escape: a 90° rotation is exactly the composition of two flips, and each flip is trivially in-place because it just swaps pairs of cells. First, transpose — reflect across the main diagonal, sending (i, j) to (j, i); rows become columns. Second, reverse every row — a horizontal mirror, sending (j, i) to (j, n - 1 - i). Chain them: (i, j) goes to (j, i), then to (j, n - 1 - i) — precisely the rotation mapping derived above. Not a coincidence to memorize; a one-line proof you can re-derive at the whiteboard.

python
n = len(matrix)
for i in range(n):
    for j in range(i + 1, n):      # j starts at i+1: touch each pair once
        matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

for row in matrix:                 # then mirror every row
    row.reverse()

The inner loop starting at j = i + 1 matters: transposing means swapping the pair (i, j) and (j, i). Loop over the whole grid and every pair gets swapped twice — back to where it started. Sweeping only above the diagonal touches each pair exactly once.

Worked Example:3×3
Original:
[1, 2, 3]
[4, 5, 6]
[7, 8, 9]

After transpose (flip across the main diagonal — rows become columns):
[1, 4, 7]
[2, 5, 8]
[3, 6, 9]

After reversing each row (horizontal mirror):
[7, 4, 1]
[8, 5, 2]
[9, 6, 3]

Check cell by cell: 1 went from (0,0) to (0,2); 8 went from (2,1) to (1,2). Both match (i, j) to (j, n-1-i).

The takeaway

Cost is O(N²) time — every cell must move, so that is optimal — and O(1) extra space: two flips, each pure swaps. The reusable idea is decomposition: a transformation that is hard to perform directly may be a chain of trivially-safe steps. It generalizes on the spot — counter-clockwise rotation is the transpose followed by reversing each column (or reverse rows first, then transpose); 180° is two 90° turns, or reverse rows and columns. Derive, don't memorize.

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