Rotate Image

Problem Description

You are given an n × n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).

You have to rotate the image in-place, which means you must modify the input 2D matrix directly. DO NOT allocate another 2D matrix to do the rotation.

Examples

Constraints

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

Transpose and Flip: A Two-Step Matrix Rotation

The obvious way to rotate an image is allocating a new matrix and copy elements: new_matrix[col][n - 1 - row] = matrix[row][col]. This uses O(n²) space, which violates the in-place constraint.

To rotate the matrix in-place, we can combine two simple matrix operations:

1. Transpose: Swap elements across the main diagonal: matrix[r][c], matrix[c][r] = matrix[c][r], matrix[r][c]. This turns rows into columns.
2. Reverse Rows: Reverse the elements in each row: matrix[r][c], matrix[r][n - 1 - c] = matrix[r][n - 1 - c], matrix[r][c].

Combining these two steps results in a clean 90-degree clockwise rotation. Both steps are executed in-place, requiring O(1) auxiliary space.

Solution 1: Transpose then Reverse Rows (In-Place)

Transpose the matrix using a nested loop starting the inner column index at the row index, then reverse each row.

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

        // Step 1: Transpose the matrix
        for (int r = 0; r < n; r++) {
            for (int c = r; c < n; c++) {
                int temp = matrix[r][c];
                matrix[r][c] = matrix[c][r];
                matrix[c][r] = temp;
            }
        }

        // Step 2: Reverse each row
        for (int r = 0; r < n; r++) {
            int left = 0;
            int right = n - 1;
            while (left < right) {
                int temp = matrix[r][left];
                matrix[r][left] = matrix[r][right];
                matrix[r][right] = temp;
                left++;
                right--;
            }
        }
    }
}

class Solution:
    def rotate(self, matrix: list[list[int]]) -> None:
        n = len(matrix)

        # Step 1: Transpose the matrix
        for r in range(n):
            for c in range(r, n):
                matrix[r][c], matrix[c][r] = matrix[c][r], matrix[r][c]

        # Step 2: Reverse each row
        for r in range(n):
            matrix[r].reverse()

#include <vector>
#include <algorithm>

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

        // Step 1: Transpose the matrix
        for (int r = 0; r < n; r++) {
            for (int c = r; c < n; c++) {
                std::swap(matrix[r][c], matrix[c][r]);
            }
        }

        // Step 2: Reverse each row
        for (int r = 0; r < n; r++) {
            std::reverse(matrix[r].begin(), matrix[r].end());
        }
    }
};

Complexity Analysis:

• Time Complexity: O(n²) where n is the dimension of the matrix. Transpose visits n²/2 elements, and reversing rows visits n²/2 elements, resulting in O(n²) total.
• Space Complexity: O(1) auxiliary space.

Where it breaks: Nothing breaks for square matrices. If the input matrix is rectangular (not square), the transpose step will fail due to index out of bounds because matrix[c][r] coordinates will exceed dimensions. This constraint is guarded by n == matrix.length == matrix[i].length.

Common Mistakes

• Starting the transpose inner loop at c = 0 instead of c = r. If you start at 0, you will swap the elements twice (e.g. swap (0, 1) to (1, 0) and then swap (1, 0) back to (0, 1)), leaving the matrix unchanged.
• Attempting to rotate a rectangular matrix using this logic. The transpose and reverse method only works for square matrices. For rectangular matrices, a separate output allocation is required.
• Reversing the columns instead of the rows. Reversing columns after transpose results in a counter-clockwise rotation instead of clockwise.

Frequently Asked Questions

How do we rotate the image 90 degrees counter-clockwise? To rotate counter-clockwise, you can either:

1. Transpose the matrix and then reverse the columns (instead of rows).
2. Reverse the rows first, and then transpose the matrix.

What is the benefit of the transpose and reverse method over rotating layer by layer? Rotating layer by layer (shifting cells in four-cycles) uses slightly fewer writes because it shifts elements directly to their final positions. However, the transpose and reverse method is much easier to write and read, which minimizes bugs during interviews.

What does this problem test in interviews? It tests your ability to manipulate 2D arrays, implement basic matrix transformations in-place, and manage swaps without extra allocations.

← All Problems