Rotate Image

Description

You are given an n × n 2D matrix representing an image. Your task is to rotate the entire image by 90 degrees clockwise.

The rotation must be done in-place — meaning you must modify the original matrix directly. You are not allowed to allocate a separate 2D matrix for the result.

After rotation, the first row of the original matrix should become the last column of the rotated matrix, the second row should become the second-to-last column, and so on.

Visual showing a 3x3 matrix before and after 90-degree clockwise rotation with arrows indicating element movement

Examples

Example 1

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

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

Explanation: After rotating the 3×3 matrix 90 degrees clockwise:

The top row [1, 2, 3] becomes the rightmost column (read top-to-bottom)
The middle row [4, 5, 6] becomes the middle column
The bottom row [7, 8, 9] becomes the leftmost column
The center element 5 stays in place

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

Explanation: After rotating the 4×4 matrix 90 degrees clockwise:

The bottom row [15, 14, 12, 16] becomes the new first column (top-to-bottom)
The top row [5, 1, 9, 11] becomes the new last column
Each element at position (i, j) moves to position (j, n-1-i) in the rotated version

Constraints

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

Editorial

Brute Force

Intuition

The simplest way to rotate a matrix 90 degrees clockwise is to create a brand new matrix and place each element directly into its rotated position.

Think of it like taking a photograph and physically turning it sideways. If you had a grid of sticky notes on a wall, you could peel each note off and place it on a new blank wall in its rotated position. The note at row i, column j in the original grid would go to row j, column (n-1-i) in the new grid.

The pattern is straightforward: for every element at position (i, j), its destination after a 90° clockwise rotation is (j, n-1-i). We iterate through every cell, copy each element to the new matrix at the computed position, and then copy the new matrix back to the original.

While this approach violates the problem's in-place constraint (since we use an extra n×n matrix), it helps us understand the fundamental transformation rule that all other approaches build upon.

Step-by-Step Explanation

Let's trace through with matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]], n = 3:

Step 1: Create a new 3×3 matrix filled with zeros: result = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]

Step 2: Process element (0, 0) = 1. Destination: (0, 3-1-0) = (0, 2). Place 1 at result[0][2].
Result: [[0, 0, 1], [0, 0, 0], [0, 0, 0]]

Step 3: Process element (0, 1) = 2. Destination: (1, 3-1-0) = (1, 2). Place 2 at result[1][2].
Result: [[0, 0, 1], [0, 0, 2], [0, 0, 0]]

Step 4: Process element (0, 2) = 3. Destination: (2, 3-1-0) = (2, 2). Place 3 at result[2][2].
Result: [[0, 0, 1], [0, 0, 2], [0, 0, 3]]

Step 5: Process element (1, 0) = 4. Destination: (0, 3-1-1) = (0, 1). Place 4 at result[0][1].
Result: [[0, 4, 1], [0, 0, 2], [0, 0, 3]]

Step 6: Process element (1, 1) = 5. Destination: (1, 3-1-1) = (1, 1). Place 5 at result[1][1].
Result: [[0, 4, 1], [0, 5, 2], [0, 0, 3]]

Step 7: Process element (1, 2) = 6. Destination: (2, 3-1-1) = (2, 1). Place 6 at result[2][1].
Result: [[0, 4, 1], [0, 5, 2], [0, 6, 3]]

Step 8: Process element (2, 0) = 7. Destination: (0, 3-1-2) = (0, 0). Place 7 at result[0][0].
Result: [[7, 4, 1], [0, 5, 2], [0, 6, 3]]

Step 9: Process element (2, 1) = 8. Destination: (1, 3-1-2) = (1, 0). Place 8 at result[1][0].
Result: [[7, 4, 1], [8, 5, 2], [0, 6, 3]]

Step 10: Process element (2, 2) = 9. Destination: (2, 3-1-2) = (2, 0). Place 9 at result[2][0].
Result: [[7, 4, 1], [8, 5, 2], [9, 6, 3]]

Step 11: Copy result back to matrix. Final: [[7, 4, 1], [8, 5, 2], [9, 6, 3]]

Brute Force — Copying Elements to New Positions — Watch each element from the original matrix being placed at its rotated position in a new result matrix, following the rule: (i, j) → (j, n-1-i).

Algorithm

Create a new n×n matrix result initialized with zeros
For each element at position (i, j) in the original matrix:
- Compute the destination: row = j, col = n - 1 - i
- Set result[j][n-1-i] = matrix[i][j]
Copy the result matrix back to the original matrix

Code

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        vector<vector<int>> result(n, vector<int>(n, 0));
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                result[j][n - 1 - i] = matrix[i][j];
            }
        }
        
        matrix = result;
    }
};

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

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        int[][] result = new int[n][n];
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                result[j][n - 1 - i] = matrix[i][j];
            }
        }
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = result[i][j];
            }
        }
    }
}

Complexity Analysis

Time Complexity: O(n²)

We visit each of the n² cells exactly once to copy it to the result matrix, and then copy the entire result back (another n² operations). Total: 2 × n² = O(n²).

Space Complexity: O(n²)

We allocate a separate n×n result matrix to hold the rotated values before copying them back. This extra space is proportional to the input size, which violates the problem's in-place requirement.

Why This Approach Is Not Efficient

The brute force approach uses O(n²) additional space for the result matrix. The problem explicitly requires an in-place rotation — meaning we must modify the original matrix without allocating another 2D matrix.

Beyond violating the constraint, using extra space is wasteful because the rotation is a deterministic rearrangement — every element has exactly one destination. If we can figure out how to move elements without losing data (by leveraging the fact that rotations form cycles of 4 elements), we can achieve O(1) extra space.

The key insight for improvement: in a 90° clockwise rotation, every element is part of a group of 4 that rotate among themselves. Element at (i, j) goes to (j, n-1-i), which goes to (n-1-i, n-1-j), which goes to (n-1-j, i), which goes back to (i, j). We can rotate all 4 in one go using a single temporary variable.

Better Approach - Four-Way Cycle Swap

Intuition

Instead of copying elements to a new matrix, we can rotate elements in-place by recognizing that every rotation consists of four-element cycles.

Imagine four people sitting at the corners of a square table. If everyone needs to move one seat clockwise, you don't need four empty chairs — you just need one person to stand up, let the person to their left slide over, and cascade the moves around the table. In matrix terms, you save one element in a temporary variable, then shift the other three into their rotated positions, and finally place the saved element into the last open spot.

For an n×n matrix, there are ⌊n/2⌋ concentric "rings" (or layers). For each ring, we process the elements along one side and perform the four-way swap for each group. The outer ring handles the border elements, the next ring handles the next layer inward, and so on until we reach the center.

Each four-way swap moves exactly 4 elements to their correct rotated positions in O(1) time. Since every element participates in exactly one cycle, the total work is O(n²) with O(1) extra space — just a single temporary variable.

Step-by-Step Explanation

Let's trace through with matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]], n = 3:

There is ⌊3/2⌋ = 1 ring (layer 0).

Ring 0 (i = 0), processing elements j from 0 to n-2-0 = 1:

Step 1: j = 0. The four positions in the cycle are:

P1 = (0, 0) = 1 (top-left corner)
P2 = (0, 2) = 3 (top-right corner)
P3 = (2, 2) = 9 (bottom-right corner)
P4 = (2, 0) = 7 (bottom-left corner)

Step 2: Save temp = P1 = 1.

Step 3: Move P4 → P1: matrix[0][0] = matrix[2][0] = 7.
Matrix: [[7, 2, 3], [4, 5, 6], [7, 8, 9]]

Step 4: Move P3 → P4: matrix[2][0] = matrix[2][2] = 9.
Matrix: [[7, 2, 3], [4, 5, 6], [9, 8, 9]]

Step 5: Move P2 → P3: matrix[2][2] = matrix[0][2] = 3.
Matrix: [[7, 2, 3], [4, 5, 6], [9, 8, 3]]

Step 6: Move temp → P2: matrix[0][2] = temp = 1.
Matrix: [[7, 2, 1], [4, 5, 6], [9, 8, 3]]

Corners are now correctly rotated!

Step 7: j = 1. The four positions are:

P1 = (0, 1) = 2
P2 = (1, 2) = 6
P3 = (2, 1) = 8
P4 = (1, 0) = 4

Step 8: Save temp = P1 = 2.

Step 9: Move P4 → P1: matrix[0][1] = matrix[1][0] = 4.
Matrix: [[7, 4, 1], [4, 5, 6], [9, 8, 3]]

Step 10: Move P3 → P4: matrix[1][0] = matrix[2][1] = 8.
Matrix: [[7, 4, 1], [8, 5, 6], [9, 8, 3]]

Step 11: Move P2 → P3: matrix[2][1] = matrix[1][2] = 6.
Matrix: [[7, 4, 1], [8, 5, 6], [9, 6, 3]]

Step 12: Move temp → P2: matrix[1][2] = temp = 2.
Matrix: [[7, 4, 1], [8, 5, 2], [9, 6, 3]]

Result: Center element 5 didn't need to move (it's a fixed point for odd n). Final matrix: [[7, 4, 1], [8, 5, 2], [9, 6, 3]] ✓

Four-Way Cycle Swap — Rotating Groups of 4 Elements — Watch how four corner/edge elements rotate among themselves using a single temporary variable. Each cycle moves 4 elements to their final positions simultaneously.

Algorithm

For each ring i from 0 to ⌊n/2⌋ - 1:
- For each position j from i to n - i - 2:
  - Identify the 4 elements in the rotation cycle:
    - P1 = matrix[i][j] (top side)
    - P2 = matrix[j][n-1-i] (right side)
    - P3 = matrix[n-1-i][n-1-j] (bottom side)
    - P4 = matrix[n-1-j][i] (left side)
  - Save temp = P1
  - P1 ← P4 (move left to top)
  - P4 ← P3 (move bottom to left)
  - P3 ← P2 (move right to bottom)
  - P2 ← temp (move saved top to right)

Code

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        for (int i = 0; i < n / 2; i++) {
            for (int j = i; j < n - i - 1; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n - 1 - j][i];
                matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];
                matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];
                matrix[j][n - 1 - i] = temp;
            }
        }
    }
};

class Solution:
    def rotate(self, matrix: list[list[int]]) -> None:
        n = len(matrix)
        for i in range(n // 2):
            for j in range(i, n - i - 1):
                temp = matrix[i][j]
                matrix[i][j] = matrix[n - 1 - j][i]
                matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j]
                matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i]
                matrix[j][n - 1 - i] = temp

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n / 2; i++) {
            for (int j = i; j < n - i - 1; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n - 1 - j][i];
                matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];
                matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];
                matrix[j][n - 1 - i] = temp;
            }
        }
    }
}

Complexity Analysis

Time Complexity: O(n²)

Each element is moved exactly once. The outer loop runs ⌊n/2⌋ times and the inner loop processes (n - 2i - 1) elements per ring. The total number of four-way swaps across all rings sums to (n² - center) / 4, and each swap does 4 assignments. So total operations = n² - (0 or 1 for center) ≈ n², giving O(n²).

Space Complexity: O(1)

We only use a single temporary variable temp to hold one element during each four-way swap. No additional data structures are created.

Why This Approach Is Not Efficient

The four-way cycle swap is already O(n²) time and O(1) space — which is optimal in terms of both. Every element must be touched at least once, so O(n²) time is a lower bound. And the in-place requirement is satisfied.

However, this approach has a practical drawback: the index arithmetic is complex and error-prone. The four positions in each cycle — (i, j), (j, n-1-i), (n-1-i, n-1-j), (n-1-j, i) — are non-trivial to derive and easy to get wrong during an interview.

There exists an equally optimal but conceptually simpler approach: decomposing the rotation into two well-known matrix operations — transpose followed by row reversal. Each operation is simple to implement correctly, and their composition produces the same 90° clockwise rotation. This makes it the preferred approach for interviews and production code.

Optimal Approach - Transpose + Reverse Rows

Intuition

Here's a beautiful mathematical insight: a 90° clockwise rotation can be decomposed into two simpler operations:

Transpose the matrix (swap rows and columns: element at (i, j) moves to (j, i))
Reverse each row (mirror each row left-to-right)

Why does this work? Let's follow the math:

After transposing: element originally at (i, j) is now at (j, i)
After reversing row j: element at (j, i) moves to (j, n-1-i)
Combined: (i, j) → (j, n-1-i) — which is exactly the 90° clockwise rotation formula!

Think of it like folding a piece of paper. The transpose is like folding along the main diagonal (top-left to bottom-right). Then reversing each row is like flipping the paper horizontally. These two simple folds together produce the same result as rotating 90° clockwise.

Both operations are straightforward to code: transpose swaps matrix[i][j] with matrix[j][i] for all i < j, and row reversal just uses a standard two-pointer swap on each row. Each is simple to implement correctly, making this approach much less error-prone than the cycle-swap method.

Step-by-Step Explanation

Let's trace through with matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]], n = 3:

Phase 1: Transpose (swap across the diagonal)

Step 1: Swap (0,1) and (1,0): swap matrix[0][1]=2 with matrix[1][0]=4.
Matrix: [[1, 4, 3], [2, 5, 6], [7, 8, 9]]

Step 2: Swap (0,2) and (2,0): swap matrix[0][2]=3 with matrix[2][0]=7.
Matrix: [[1, 4, 7], [2, 5, 6], [3, 8, 9]]

Step 3: Swap (1,2) and (2,1): swap matrix[1][2]=6 with matrix[2][1]=8.
Matrix: [[1, 4, 7], [2, 5, 8], [3, 6, 9]]

Transpose complete! Rows have become columns and vice versa.

Phase 2: Reverse each row

Step 4: Reverse row 0: [1, 4, 7] → swap indices 0 and 2: [7, 4, 1].
Matrix: [[7, 4, 1], [2, 5, 8], [3, 6, 9]]

Step 5: Reverse row 1: [2, 5, 8] → swap indices 0 and 2: [8, 5, 2].
Matrix: [[7, 4, 1], [8, 5, 2], [3, 6, 9]]

Step 6: Reverse row 2: [3, 6, 9] → swap indices 0 and 2: [9, 6, 3].
Matrix: [[7, 4, 1], [8, 5, 2], [9, 6, 3]]

Result: [[7, 4, 1], [8, 5, 2], [9, 6, 3]] — correctly rotated 90° clockwise!

Transpose + Reverse Rows — Two Simple Steps to Rotate — Watch the matrix first get transposed (rows become columns), then each row gets reversed. These two simple operations together produce a 90° clockwise rotation.

Algorithm

Transpose the matrix:
- For each pair (i, j) where i < j:
  - Swap matrix[i][j] with matrix[j][i]
- This converts rows into columns
Reverse each row:
- For each row i from 0 to n-1:
  - Use two pointers (left = 0, right = n-1) and swap elements moving inward
- This mirrors each row horizontally

The composition of these two operations produces a 90° clockwise rotation because:

Transpose: (i, j) → (j, i)
Row reverse: (j, i) → (j, n-1-i)
Combined: (i, j) → (j, n-1-i) ← the rotation formula

Code

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        
        // Step 1: Transpose the matrix
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                swap(matrix[i][j], matrix[j][i]);
            }
        }
        
        // Step 2: Reverse each row
        for (int i = 0; i < n; i++) {
            reverse(matrix[i].begin(), matrix[i].end());
        }
    }
};

class Solution:
    def rotate(self, matrix: list[list[int]]) -> None:
        n = len(matrix)
        
        # Step 1: Transpose the matrix
        for i in range(n):
            for j in range(i + 1, n):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        
        # Step 2: Reverse each row
        for i in range(n):
            matrix[i].reverse()

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        
        // Step 1: Transpose the matrix
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
        
        // Step 2: Reverse each row
        for (int i = 0; i < n; i++) {
            int left = 0, right = n - 1;
            while (left < right) {
                int temp = matrix[i][left];
                matrix[i][left] = matrix[i][right];
                matrix[i][right] = temp;
                left++;
                right--;
            }
        }
    }
}

Complexity Analysis

Time Complexity: O(n²)

The transpose step visits each pair (i, j) with i < j exactly once, performing n(n-1)/2 swaps. The row reversal step processes each of the n rows, performing ⌊n/2⌋ swaps per row, for a total of n × ⌊n/2⌋ swaps. Combined: approximately n² operations total, giving O(n²). This is optimal since we must touch every element at least once.

Space Complexity: O(1)

Both the transpose and row reversal are done in-place using only a single temporary variable for swaps. No additional data structures are allocated. This satisfies the problem's in-place requirement.

EASY

MEDIUM

EASY

MEDIUM

EASY

MEDIUM

HARD

EASY

MEDIUM

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

HARD

MEDIUM

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

MEDIUM

MEDIUM

EASY

MEDIUM

MEDIUM

EASY

MEDIUM

Rotate Image

Description

Examples

Example 1

Example 2

Constraints

Editorial

Brute Force

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Better Approach - Four-Way Cycle Swap

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Optimal Approach - Transpose + Reverse Rows

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis