Rotate Image (LC 48): Transpose and Reverse In Place

Rotate an n x n matrix 90 degrees clockwise in place. Transpose the matrix, then reverse each row, or rotate cells four at a time layer by layer. O(n^2) time and O(1) extra space.

Language Selection

Choose your preferred programming language

Showing: Python

Rotate Image

Problem Statement

You are given a square grid of integers, matrix, with n rows and n columns. It represents an image. Turn the image a quarter turn clockwise (90 degrees).

The rotation must happen in place: change the values inside matrix itself. Do not build a second n x n matrix and return it. The function returns nothing.

After a clockwise turn, the first row of the original becomes the last column, the second row becomes the second-to-last column, and so on. In index terms, the value at matrix[i][j] moves to position [j][n - 1 - i].

Examples

Example 1:

Input: matrix = [[1,2],[3,4]]
Output: [[3,1],[4,2]]
Explanation: The top row [1,2] becomes the right column, and the bottom row [3,4] becomes the left column.

Example 2:

Input: matrix = [[10,20,30],[40,50,60],[70,80,90]]
Output: [[70,40,10],[80,50,20],[90,60,30]]
Explanation: Reading the original first column from bottom to top (70, 40, 10) gives the new first row.

Example 3:

Input: matrix = [[-7]]
Output: [[-7]]
Explanation: A 1 x 1 matrix looks the same after any rotation.

Constraints

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

Approach 1: Copy Into a Second Matrix

Algorithm

The simplest idea follows the index rule directly. Write every value into its rotated position in a new matrix, then copy that matrix back into the input. This breaks the in-place rule, but it is a good way to check that you have the mapping right before you optimize.

  1. Create an n x n matrix rotated.
  2. For every cell (i, j), set rotated[j][n - 1 - i] = matrix[i][j].
  3. Copy every row of rotated back into matrix.

Implementation

Python:

from typing import List


class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        n = len(matrix)
        rotated = [[0] * n for _ in range(n)]
        # Row i of the original becomes column n - 1 - i of the result
        for i in range(n):
            for j in range(n):
                rotated[j][n - 1 - i] = matrix[i][j]
        # Write back so the caller's matrix holds the answer
        for i in range(n):
            matrix[i][:] = rotated[i]

Java:

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        int[][] rotated = new int[n][n];
        // Row i of the original becomes column n - 1 - i of the result
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                rotated[j][n - 1 - i] = matrix[i][j];
            }
        }
        // Copy back into the caller's matrix
        for (int i = 0; i < n; i++) {
            System.arraycopy(rotated[i], 0, matrix[i], 0, n);
        }
    }
}

Go:

func rotate(matrix [][]int) {
    n := len(matrix)
    rotated := make([][]int, n)
    for i := range rotated {
        rotated[i] = make([]int, n)
    }
    // Row i of the original becomes column n-1-i of the result
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            rotated[j][n-1-i] = matrix[i][j]
        }
    }
    // Copy back into the caller's matrix
    for i := 0; i < n; i++ {
        copy(matrix[i], rotated[i])
    }
}

JavaScript:

/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
var rotate = function(matrix) {
    const n = matrix.length;
    const rotated = Array.from({ length: n }, () => new Array(n).fill(0));
    // Row i of the original becomes column n - 1 - i of the result
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            rotated[j][n - 1 - i] = matrix[i][j];
        }
    }
    // Copy back into the caller's matrix
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            matrix[i][j] = rotated[i][j];
        }
    }
};

C#:

public class Solution {
    public void Rotate(int[][] matrix) {
        int n = matrix.Length;
        var rotated = new int[n, n];
        // Row i of the original becomes column n - 1 - i of the result
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                rotated[j, n - 1 - i] = matrix[i][j];
            }
        }
        // Copy back into the caller's matrix
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = rotated[i, j];
            }
        }
    }
}

C++:

#include <vector>
using namespace std;

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = static_cast<int>(matrix.size());
        vector<vector<int>> rotated(n, vector<int>(n));
        // Row i of the original becomes column n - 1 - i of the result
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                rotated[j][n - 1 - i] = matrix[i][j];
            }
        }
        // Copy back into the caller's matrix
        matrix = rotated;
    }
};

Complexity Analysis

  • Time: O(n^2). Each cell is written once into rotated and once back into matrix.
  • Space: O(n^2) for the second matrix, which is why this does not meet the in-place requirement.

Approach 2: Transpose, Then Reverse Each Row (Optimal)

Algorithm

A clockwise rotation can be split into two simple moves that each work in place:

  • Transpose (flip across the main diagonal): (i, j) goes to (j, i).
  • Reverse each row (flip left to right): (j, i) goes to (j, n - 1 - i).

Together they send (i, j) to (j, n - 1 - i), which is exactly the clockwise rule.

  1. For every pair with i < j, swap matrix[i][j] and matrix[j][i]. Only the upper triangle is visited, so each pair is swapped once.
  2. Reverse every row.

Implementation

Python:

from typing import List


class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        n = len(matrix)
        # Step 1: transpose by swapping across the main 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]
        # Step 2: reverse each row
        for row in matrix:
            row.reverse()

Java:

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        // Step 1: transpose by swapping across the main diagonal
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = tmp;
            }
        }
        // Step 2: reverse each row with two pointers
        for (int[] row : matrix) {
            for (int l = 0, r = n - 1; l < r; l++, r--) {
                int tmp = row[l];
                row[l] = row[r];
                row[r] = tmp;
            }
        }
    }
}

Go:

func rotate(matrix [][]int) {
    n := len(matrix)
    // Step 1: transpose by swapping across the main diagonal
    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        }
    }
    // Step 2: reverse each row with two pointers
    for _, row := range matrix {
        for l, r := 0, n-1; l < r; l, r = l+1, r-1 {
            row[l], row[r] = row[r], row[l]
        }
    }
}

JavaScript:

/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
var rotate = function(matrix) {
    const n = matrix.length;
    // Step 1: transpose by swapping across the main diagonal
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
        }
    }
    // Step 2: reverse each row
    for (const row of matrix) {
        row.reverse();
    }
};

C#:

using System;

public class Solution {
    public void Rotate(int[][] matrix) {
        int n = matrix.Length;
        // Step 1: transpose by swapping across the main diagonal
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                (matrix[i][j], matrix[j][i]) = (matrix[j][i], matrix[i][j]);
            }
        }
        // Step 2: reverse each row
        foreach (int[] row in matrix) {
            Array.Reverse(row);
        }
    }
}

C++:

#include <algorithm>
#include <utility>
#include <vector>
using namespace std;

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = static_cast<int>(matrix.size());
        // Step 1: transpose by swapping across the main diagonal
        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 (auto& row : matrix) {
            reverse(row.begin(), row.end());
        }
    }
};

Complexity Analysis

  • Time: O(n^2). The transpose touches about n^2 / 2 pairs and the row reversals touch every cell once.
  • Space: O(1). Only a few loop variables and a temporary for swapping.

Approach 3: Rotate Four Cells at a Time

Algorithm

Under a quarter turn, cells move in cycles of four: a cell on the top edge moves to the right edge, the right edge cell moves to the bottom, the bottom one moves to the left, and the left one moves to the top. We can rotate each cycle directly with one temporary variable.

Work from the outside in. Layer i is the ring whose top row is row i. In that ring, walk the top edge from column i to column n - 2 - i (the last corner belongs to the next edge’s cycle). For each position j, the four cells of its cycle are:

  • top: (i, j)
  • right: (j, n - 1 - i)
  • bottom: (n - 1 - i, n - 1 - j)
  • left: (n - 1 - j, i)
  1. Save the top value.
  2. Move left into top, bottom into left, right into bottom.
  3. Put the saved value into right.
  4. Repeat for every j in the layer and for each of the n / 2 layers. When n is odd, the center cell does not move.

Implementation

Python:

from typing import List


class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        n = len(matrix)
        for i in range(n // 2):  # one ring per iteration, outside in
            for j in range(i, n - 1 - i):
                top = matrix[i][j]
                matrix[i][j] = matrix[n - 1 - j][i]                  # left -> top
                matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j]  # bottom -> left
                matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i]  # right -> bottom
                matrix[j][n - 1 - i] = top                           # top -> right

Java:

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n / 2; i++) {          // one ring per iteration
            for (int j = i; j < n - 1 - i; j++) {
                int top = matrix[i][j];
                matrix[i][j] = matrix[n - 1 - j][i];                 // left -> top
                matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j]; // bottom -> left
                matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i]; // right -> bottom
                matrix[j][n - 1 - i] = top;                          // top -> right
            }
        }
    }
}

Go:

func rotate(matrix [][]int) {
    n := len(matrix)
    for i := 0; i < n/2; i++ { // one ring per iteration
        for j := i; j < n-1-i; j++ {
            top := matrix[i][j]
            matrix[i][j] = matrix[n-1-j][i]             // left -> top
            matrix[n-1-j][i] = matrix[n-1-i][n-1-j]     // bottom -> left
            matrix[n-1-i][n-1-j] = matrix[j][n-1-i]     // right -> bottom
            matrix[j][n-1-i] = top                      // top -> right
        }
    }
}

JavaScript:

/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
var rotate = function(matrix) {
    const n = matrix.length;
    for (let i = 0; i < Math.floor(n / 2); i++) { // one ring per iteration
        for (let j = i; j < n - 1 - i; j++) {
            const top = matrix[i][j];
            matrix[i][j] = matrix[n - 1 - j][i];                 // left -> top
            matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j]; // bottom -> left
            matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i]; // right -> bottom
            matrix[j][n - 1 - i] = top;                          // top -> right
        }
    }
};

C#:

public class Solution {
    public void Rotate(int[][] matrix) {
        int n = matrix.Length;
        for (int i = 0; i < n / 2; i++) {          // one ring per iteration
            for (int j = i; j < n - 1 - i; j++) {
                int top = matrix[i][j];
                matrix[i][j] = matrix[n - 1 - j][i];                 // left -> top
                matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j]; // bottom -> left
                matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i]; // right -> bottom
                matrix[j][n - 1 - i] = top;                          // top -> right
            }
        }
    }
}

C++:

#include <vector>
using namespace std;

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = static_cast<int>(matrix.size());
        for (int i = 0; i < n / 2; i++) {          // one ring per iteration
            for (int j = i; j < n - 1 - i; j++) {
                int top = matrix[i][j];
                matrix[i][j] = matrix[n - 1 - j][i];                 // left -> top
                matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j]; // bottom -> left
                matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i]; // right -> bottom
                matrix[j][n - 1 - i] = top;                          // top -> right
            }
        }
    }
};

Complexity Analysis

  • Time: O(n^2). Every cell is moved exactly once (four per cycle, about n^2 / 4 cycles).
  • Space: O(1). One temporary value per cycle.

Key Insights

  1. One index rule drives everything: clockwise rotation sends (i, j) to (j, n - 1 - i). Derive it once from a small example and every approach follows.
  2. Compose simple flips: a rotation equals a transpose followed by a horizontal flip. Each flip is easy to do in place, so the rotation is too.
  3. Cycles of four: each cell belongs to a group of four that trade places. Rotating a group needs only one temporary value.
  4. Direction is a choice of flip: transpose then reverse each row is clockwise. Transpose then reverse each column (that is, reverse the order of the rows) gives counterclockwise.

Edge Cases

  1. 1 x 1 matrix: nothing moves. Both in-place approaches skip all work correctly.
  2. 2 x 2 matrix: a single four-cell cycle, [[1,2],[3,4]] becomes [[3,1],[4,2]].
  3. Odd n: the center cell stays put. The layer loop runs n / 2 times (rounded down) and never touches it.
  4. Repeated or negative values: the algorithm only moves values, so duplicates and negatives need no special care.

Common Mistakes

  1. Swapping the full matrix during transpose: looping j over all columns swaps every pair twice and leaves the matrix unchanged. Start j at i + 1.
  2. Reversing in the wrong direction: reversing the order of rows (instead of each row’s contents) after a transpose gives a counterclockwise turn.
  3. Overwriting before saving: in the four-way rotation, assigning in the wrong order loses a value. Save one cell first, then fill each slot from the cell that moves into it.
  4. Off-by-one on the inner loop: iterating j up to n - 1 - i inclusive rotates the corner twice. The bound is exclusive.
  5. Returning a new matrix: the caller’s matrix must change. In Python, matrix = rotated only rebinds the local name.

Interview Tips

  1. Start with the mapping: write out a 3 x 3 example and state the (i, j) -> (j, n - 1 - i) rule before coding.
  2. Mention the extra-matrix version, then improve: it shows you understand the mapping and sets up the in-place discussion.
  3. Prefer transpose + reverse for clarity: it is short and hard to get wrong. Offer the four-way cycle if the interviewer wants a single pass.
  4. Trace a 2 x 2 by hand: it catches most index errors in under a minute.

Follow-up Questions

  1. Counterclockwise rotation? Transpose, then reverse each column (or reverse each row first, then transpose).
  2. Rotate by 180 degrees? Reverse the order of rows and reverse each row, or apply the 90-degree rotation twice.
  3. Rectangular m x n matrix? It cannot be rotated in place because the shape changes to n x m. Build a new matrix with result[j][m - 1 - i] = matrix[i][j].
  4. Rotate by k quarter turns? Rotate k mod 4 times, or pick the single flip combination for that angle.