Rotate Image

Given a square n × n matrix of integers matrix, rotate it by 90 degrees clockwise.

You must rotate the matrix in-place. Do not allocate another 2D matrix and do the rotation.

Examples

• n == matrix.length == matrix[i].length
• 1 ≤ n ≤ 20
• -1000 ≤ matrix[i][j] ≤ 1000

Prerequisites

Before attempting this problem, you should be comfortable with:

• 2D Array Indexing — understanding how to access and modify elements using row and column indices
• Matrix Transpose — swapping elements across the main diagonal where element (i, j) swaps with (j, i)
• In-Place Manipulation — rotating elements within the matrix without using additional space for a copy
• Layer-by-Layer Processing — processing a matrix from outer boundaries inward, handling four elements at a time

1. Brute Force (Extra Matrix)

Intuition

A direct beginner-friendly approach: create a new matrix where each element from the original matrix is placed in its rotated position, then copy it back. The key observation for a 90° clockwise rotation is that an element at position (i, j) moves to position (j, n-1-i).

Algorithm

• Create a new n × n matrix rotated filled with zeros.
• For every element matrix[i][j], place it at rotated[j][n-1-i].
• Copy rotated back into matrix row by row.

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

        for i in range(n):
            for j in range(n):
                rotated[j][n - 1 - i] = matrix[i][j]

        for i in range(n):
            for j in range(n):
                matrix[i][j] = rotated[i][j]

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        int[][] rotated = new int[n][n];

        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                rotated[j][n - 1 - i] = matrix[i][j];

        for (int i = 0; i < n; i++)
            matrix[i] = rotated[i];
    }
}

Time Complexity: O(n²)
Space Complexity: O(n²) — the extra rotated matrix.

2. Rotate By Four Cells (Layer-by-Layer)

Intuition

Instead of extra space, rotate layer by layer — starting from the outermost ring and moving inward. For each layer, elements move in groups of four. When you rotate 90° clockwise, four cells form a cycle:

• top-left → top-right
• top-right → bottom-right
• bottom-right → bottom-left
• bottom-left → top-left

By saving just one value temporarily (first), we rotate all four positions using only O(1) extra space. We repeat this for every position in each layer and move inward until the entire matrix is done.

Algorithm

• Initialize l = 0, r = n - 1 as the current layer boundaries.
• While l < r, for each offset i from 0 to r - l - 1:
• Set top = l, bottom = r.
• Save first = matrix[top][l+i] (top-left).
• Move bottom-left → top-left: matrix[top][l+i] = matrix[bottom-i][l]
• Move bottom-right → bottom-left: matrix[bottom-i][l] = matrix[bottom][r-i]
• Move top-right → bottom-right: matrix[bottom][r-i] = matrix[top+i][r]
• Move saved top-left → top-right: matrix[top+i][r] = first
• After each layer, increment l and decrement r.

3. Reverse + Transpose (Optimal)

Intuition

A 90° clockwise rotation can be decomposed into two simple in-place operations:

• Step 1 — Reverse rows vertically: Swap row 0 with row n-1, row 1 with row n-2, etc. Element at (i, j) moves to (n-1-i, j).
• Step 2 — Transpose across the main diagonal: Swap matrix[i][j] with matrix[j][i] for all i < j. Element at (n-1-i, j) moves to (j, n-1-i).

After both steps, element originally at (i, j) ends up at (j, n-1-i) — exactly the destination for a 90° clockwise rotation. This is preferred over four-cell because the code is significantly simpler to read and verify.

Algorithm

• Call matrix.reverse() to flip rows vertically.
• For all i from 0 to n-1, and all j from i+1 to n-1: swap matrix[i][j] with matrix[j][i].

Common Pitfalls

Confusing Clockwise and Counter-Clockwise Rotation

The order of operations matters: for 90° clockwise, reverse rows first then transpose. For counter-clockwise, transpose first then reverse rows. Mixing up this order produces incorrect rotations.

Transposing the Entire Matrix Instead of Upper Triangle

When transposing in-place, starting the inner loop at j = 0 instead of j = i + 1 swaps each element twice — returning the matrix to its original state. Always ensure j starts at i + 1.

# Wrong: swaps every pair twice → no change
for i in range(n):
    for j in range(n):  # j starts at 0!
        matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

# Correct: only upper triangle
for i in range(n):
    for j in range(i + 1, n):
        matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

Incorrect Index Calculation in Layer-by-Layer Rotation

In the four-cell approach, mixing up top, bottom, l, r, and the offset i causes elements to land in the wrong positions. The four assignments must follow the exact clockwise order: bottom-left → top-left → (save), bottom-right → bottom-left, top-right → bottom-right, saved → top-right.