136.Rotate Image

MediumBlind 75Math & Geometry · 1/8

Problem

You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees clockwise.

The rotation must be done in place — modify matrix directly; do not allocate another 2D matrix to hold the result.

Examples

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

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

💡 Key Insight

A clockwise rotation sends cell (r, c) to (c, n - 1 - r). That mapping is a transpose ((r, c) → (c, r)) followed by a horizontal flip of each row ((c, r) → (c, n - 1 - r)) — two simple in-place passes. Alternatively, cells move in cycles of four around each square ring, and you can rotate each cycle with a single temporary variable.

Extra Matrix (Brute Force)

TimeO(n²)SpaceO(n²)

Intuition

Write each element straight to its rotated position in a copy, then copy back. The rule: element at row r, column c ends up at row c, column n - 1 - r (the first row becomes the last column).

Algorithm

Create rotated[n][n].
For every (r, c): rotated[c][n - 1 - r] = matrix[r][c].
Copy rotated back into matrix row by row.

Visualization

matrix          rotated
1 2 3           7 4 1
4 5 6    -->    8 5 2
7 8 9           9 6 3

row 0 (1,2,3) becomes column 2 read top-down
row 2 (7,8,9) becomes column 0 read top-down

Code

java

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        int[][] rotated = new int[n][n];
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                rotated[c][n - 1 - r] = matrix[r][c]; // row r becomes column n-1-r
            }
        }
        for (int r = 0; r < n; r++) {
            System.arraycopy(rotated[r], 0, matrix[r], 0, n);
        }
    }
}

Complexity

Time: O(n²) — every cell is written twice.
Space: O(n²) — the extra matrix (violates the in-place requirement).

Rotate Four Cells at a Time

TimeO(n²)SpaceO(1)

Intuition

Peel the matrix into concentric square rings. In a ring, four cells form a cycle: top → right → bottom → left → top. Save the top one in tmp and shift the other three along, then put tmp in the right slot. Process n / 2 rings, and in each ring every offset i along the side.

Algorithm

For layer from 0 to n / 2 - 1: let first = layer, last = n - 1 - layer.
For i from first to last - 1, with offset = i - first:
- tmp = top = matrix[first][i].
- top ← left = matrix[last - offset][first].
- left ← bottom = matrix[last][last - offset].
- bottom ← right = matrix[i][last].
- right ← tmp.

Visualization

layer 0, i = 0 on a 3x3 (corners)
1 . 3        7 . 1
. . .   -->  . . .
7 . 9        9 . 3

layer 0, i = 1 (edge middles)
. 2 .        . 4 .
4 . 6   -->  8 . 2
. 8 .        . 6 .

Code

java

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int layer = 0; layer < n / 2; layer++) {
            int first = layer, last = n - 1 - layer;
            for (int i = first; i < last; i++) {
                int offset = i - first;
                int top = matrix[first][i];                              // save top
                matrix[first][i] = matrix[last - offset][first];         // left   -> top
                matrix[last - offset][first] = matrix[last][last - offset]; // bottom -> left
                matrix[last][last - offset] = matrix[i][last];           // right  -> bottom
                matrix[i][last] = top;                                   // top    -> right
            }
        }
    }
}

Complexity

Time: O(n²) — each cell is moved exactly once.
Space: O(1) — a single temporary variable.

Transpose + Reverse RowsOptimal

TimeO(n²)SpaceO(1)

Intuition

Break the rotation into two easy-to-get-right mirror operations:

Transpose — swap matrix[r][c] with matrix[c][r] for c > r. Rows become columns.
Reverse each row — mirror left-to-right.

Composition: (r, c) → (c, r) → (c, n - 1 - r), exactly the clockwise mapping. Same O(n²) / O(1) as the ring method, but far less index juggling.

Algorithm

For r in 0..n-1, for c in r+1..n-1: swap matrix[r][c] and matrix[c][r].
For each row, swap row[left] and row[right] while left < right.

Visualization

flowchart LR
    A["1 2 3<br/>4 5 6<br/>7 8 9"] -->|"transpose"| B["1 4 7<br/>2 5 8<br/>3 6 9"]
    B -->|"reverse each row"| C["7 4 1<br/>8 5 2<br/>9 6 3"]

Code

java

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        // 1) transpose: only the upper triangle, otherwise we swap twice
        for (int r = 0; r < n; r++) {
            for (int c = r + 1; c < n; c++) {
                int tmp = matrix[r][c];
                matrix[r][c] = matrix[c][r];
                matrix[c][r] = tmp;
            }
        }
        // 2) reverse every row
        for (int[] row : matrix) {
            for (int left = 0, right = n - 1; left < right; left++, right--) {
                int tmp = row[left];
                row[left] = row[right];
                row[right] = tmp;
            }
        }
    }
}

Complexity

Time: O(n²) — each cell is touched a constant number of times.
Space: O(1) — swaps only.

Complexity Comparison

Approach	Time	Space
Extra Matrix	O(n²)	O(n²)
Four-way Cycle	O(n²)	O(1)
Transpose + Reverse	O(n²)	O(1)

Common Pitfalls

Transposing over the full matrix (c from 0) — each pair is swapped twice and the matrix ends up unchanged.
Reversing columns instead of rows after the transpose — that rotates counter-clockwise.
Assigning matrix = rotated in Approach 1 — that only rebinds the local reference; the caller's matrix is untouched.
In the ring method, looping i up to last inclusive — the corner would be rotated twice.