Rotate Image

medium
Arrays & HashingArrayMatrixMath

You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees clockwise. You must rotate the matrix in place, meaning you need to modify the input matrix directly. Do not allocate another 2D matrix for the rotation.

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: The matrix is rotated 90 degrees clockwise.

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

Constraints

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

Approaches

2 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Rotate Four Cells at a Time

Intuition

Process the matrix layer by layer from the outside in. For each layer, rotate groups of four elements that form a cycle. The element at position (i, j) moves to (j, n-1-i), which moves to (n-1-i, n-1-j), which moves to (n-1-j, i), which moves back to (i, j). By rotating these four positions simultaneously using a temporary variable, we perform the rotation in place without needing extra space.

Algorithm

  1. For each layer from 0 to n/2 - 1 (outer loop variable i):
  2. For each position in the current layer from i to n-1-i-1 (inner loop variable j):
  3. Save matrix[i][j] in a temp variable.
  4. Move the left element to the top: matrix[i][j] = matrix[n-1-j][i].
  5. Move the bottom element to the left: matrix[n-1-j][i] = matrix[n-1-i][n-1-j].
  6. Move the right element to the bottom: matrix[n-1-i][n-1-j] = matrix[j][n-1-i].
  7. Move temp to the right: matrix[j][n-1-i] = temp.
TimeO(n^2)SpaceO(1)

Code (C++ · Java · Python · Go)

C++17
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 - 1 - i; 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;
            }
        }
    }
};
Java 21
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 - 1 - i; 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;
            }
        }
    }
}
Python 3.12
def rotate(matrix: list[list[int]]) -> None:
    n = len(matrix)
    for i in range(n // 2):
        for j in range(i, n - 1 - i):
            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
Go 1.26
func rotate(matrix [][]int) {
    n := len(matrix)
    for i := 0; i < n/2; i++ {
        for j := i; j < n-1-i; j++ {
            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
        }
    }
}
Approach 2

Transpose Then Reverse

Intuition

A 90-degree clockwise rotation can be decomposed into two simpler operations: first transpose the matrix (swap rows and columns), then reverse each row. Transposing converts matrix[i][j] to matrix[j][i]. Then reversing each row achieves the final clockwise rotation. This decomposition makes the code cleaner and easier to understand compared to the four-way swap.

Algorithm

  1. Transpose the matrix: for each cell where i < j, swap matrix[i][j] with matrix[j][i].
  2. Reverse each row of the transposed matrix.
TimeO(n^2)SpaceO(1)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();

        // Transpose
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                swap(matrix[i][j], matrix[j][i]);
            }
        }

        // Reverse each row
        for (int i = 0; i < n; i++) {
            reverse(matrix[i].begin(), matrix[i].end());
        }
    }
};
Java 21
class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;

        // Transpose
        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;
            }
        }

        // 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--;
            }
        }
    }
}
Python 3.12
def rotate(matrix: list[list[int]]) -> None:
    n = len(matrix)

    # Transpose
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

    # Reverse each row
    for i in range(n):
        matrix[i].reverse()
Go 1.26
func rotate(matrix [][]int) {
    n := len(matrix)

    // Transpose
    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]
        }
    }

    // Reverse each row
    for i := 0; i < n; i++ {
        left, right := 0, n-1
        for left < right {
            matrix[i][left], matrix[i][right] = matrix[i][right], matrix[i][left]
            left++
            right--
        }
    }
}

Frequently asked questions

What is the optimal time complexity of Rotate Image?

The most efficient approach in this guide ("Transpose Then Reverse") runs in O(n^2) time and uses O(1) extra space. Earlier brute-force approaches are slower; see all 2 approaches above for the full progression.

What pattern does Rotate Image use?

Rotate Image is a medium-level Arrays & Hashing problem involving Array, Matrix, Math. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Rotate Image be solved without extra space?

The most space-efficient approach in this guide uses O(1) extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(1), while the optimized version uses O(1).

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Related Problems

Spiral Matrix

Original problem: leetcode.com

Loading editor...
Input
matrix=
[[1,2,3],[4,5,6],[7,8,9]]
Expected Output
[[7,4,1],[8,5,2],[9,6,3]]