Rotate Image

Medium Problem 30 of 151 Java and Python

Problem

You are given an n × n 2D matrix representing an image. Rotate it by 90 degrees clockwise, in place: modify the input matrix directly without allocating another matrix.

Example 1

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

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

1 ≤ n ≤ 20
-1000 ≤ matrix[i][j] ≤ 1000

Explanation

After a clockwise rotation, the value at (i, j) ends up at (j, n - 1 - i).

That move splits into two easy in-place steps: transpose (swap (i, j) with (j, i)) and then reverse each row.

Approach 1 · Naive

Copy into a new matrix

Time O(n²)
Space O(n²)

Write each value into its rotated position in a copy, then copy it back. Simple, but it uses the extra matrix the problem forbids.

Create rotated of size n × n.
Set rotated[j][n - 1 - i] = matrix[i][j] for every cell.
Copy rotated back into matrix.

Java

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].clone();
        }
    }
}

Python

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]
        matrix[:] = rotated

Approach 2 · Optimal

Transpose, then reverse rows

Time O(n²)
Space O(1)

Swap across the main diagonal, then reverse every row. Both steps are in place.

For i < j, swap matrix[i][j] with matrix[j][i].
Reverse each row.

Java

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        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;
            }
        }
        for (int[] row : matrix) {
            for (int left = 0, right = n - 1; left < right; left++, right--) {
                int temp = row[left];
                row[left] = row[right];
                row[right] = temp;
            }
        }
    }
}

Python

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        n = len(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]
        for row in matrix:
            row.reverse()

Complexity compared

Approach	Time	Space
Naive Copy into a new matrix	O(n²)	O(n²)
Optimal Transpose, then reverse rows	O(n²)	O(1)

Key takeaways

Counter-clockwise: transpose, then reverse each column (or reverse rows first, then transpose).
Only loop j > i while transposing, or every pair gets swapped twice and nothing changes.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem