LeetCode Rotate Image: Transpose Plus Reverse

Rotate Image (LeetCode 48, Medium) asks you to rotate an n by n matrix 90 degrees clockwise in place. 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]]

Brute Force

Allocate a new matrix and copy matrix[i][j] into result[j][n-1-i].

def rotate_brute(matrix):
    n = len(matrix)
    result = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            result[j][n - 1 - i] = matrix[i][j]
    return result

Correct but uses O(n^2) extra space and does not mutate in place.

Optimal Solution

Two-step in-place rotation: transpose (swap across the main diagonal), then reverse each row.

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()

Both passes are O(n^2) total cell touches with O(1) extra space.

Walk Through an 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.

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

• LeetCode 54 Spiral Matrix
• LeetCode 59 Spiral Matrix II
• LeetCode 73 Set Matrix Zeroes (in-place tricks)
• LeetCode 867 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.