Rotate Image — Transpose Plus Row Reverse

Rotating an n by n matrix 90 degrees clockwise in place looks tricky, but the slickest answer is two passes: transpose, then reverse each row.

The Problem

Given an n by n 2D integer matrix, rotate it 90 degrees clockwise. You must do this in place; you cannot allocate another n by n matrix.

Example:

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

Intuition

Transpose maps cell (i, j) to (j, i). Then reversing each row maps (j, i) to (j, n-1-i). Composed, (i, j) ends up at (j, n-1-i), which is exactly a 90 degree clockwise rotation. Both operations are in place. The only subtle bit is making the transpose loop iterate over the upper triangle (j > i) so we don’t swap the same pair back.

Explanation with Example

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

Transpose:

• Swap (0,1) and (1,0). Matrix [[1,4,3],[2,5,6],[7,8,9]].
• Swap (0,2) and (2,0). Matrix [[1,4,7],[2,5,6],[3,8,9]].
• Swap (1,2) and (2,1). Matrix [[1,4,7],[2,5,8],[3,6,9]].

Reverse each row:

• Row 0 becomes [7,4,1].
• Row 1 becomes [8,5,2].
• Row 2 becomes [9,6,3].

Final matrix matches the expected output.

start:           after transpose:      after row reverse:
[1 2 3]          [1 4 7]               [7 4 1]
[4 5 6]   -->    [2 5 8]      -->      [8 5 2]
[7 8 9]          [3 6 9]               [9 6 3]

cell (i,j) trajectory:
start at (i, j)
transpose to (j, i)
reverse row to (j, n-1-i)
this is exactly 90 deg clockwise.

Code

def rotate(matrix):
    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()

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 tmp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = tmp;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int l = 0, r = n - 1; l < r; l++, r--) {
            int tmp = matrix[i][l];
            matrix[i][l] = matrix[i][r];
            matrix[i][r] = tmp;
        }
    }
}

void rotate(vector<vector<int>>& matrix) {
    int n = matrix.size();
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            std::swap(matrix[i][j], matrix[j][i]);
    for (auto& row : matrix)
        std::reverse(row.begin(), row.end());
}

Edge Cases

• n = 0: nothing to do.
• n = 1: single cell; rotation is a no-op.
• Even n: the transpose loop still works correctly because j starts at i + 1.
• Counter-clockwise rotation: transpose then reverse each column instead, or reverse rows first then transpose.
• 180 degree rotation: reverse rows then reverse each row, or just swap symmetric pairs.

Complexity Analysis

• Time: O(n^2). Every cell is touched a constant number of times.
• Space: O(1) extra. We mutate in place.

The four-cell swap alternative achieves the same complexity but is harder to write correctly under time pressure. The transpose-reverse approach is the standard.

How to Explain It in an Interview

Sketch a 3x3 grid on the whiteboard and circle one cell’s path through both operations. Say: “Transpose maps (i, j) to (j, i). Then reversing each row maps (j, i) to (j, n-1-i). Composed, (i, j) ends up at (j, n-1-i), which is exactly a 90 degree clockwise rotation.” That two-line proof sells the approach. Show that the transpose loop runs over the upper triangle (j > i) so we don’t undo our own swaps.

Related Problems

• Spiral Matrix
• Spiral Matrix II
• Set Matrix Zeroes (in-place tricks)
• Transpose Matrix

Wrap up

Rotate Image is the cleanest demo that decomposition can beat clever ad-hoc swaps. Transpose plus reverse is short, readable, and obviously correct. Keep that decomposition in mind: any rotation or reflection on a square matrix can be expressed as a composition of transposes and reverses.