48. Rotate Image

Quick Identifier

Topic: arrays-hashing
Pattern: Matrix Math (Transpose + Reverse)
Hint: Don't try to cycle 4 elements at a time; the loop boundaries are a nightmare. Use linear algebra: a 90° clockwise rotation is mathematically identical to a Transpose followed by a Horizontal Reflection.
Difficulty: Medium
Companies: Amazon, Google, Meta, Microsoft, Apple
LeetCode: 48

Quick Sights

Time Complexity: O(N^2). We visit each of the $N \times N$ cells twice (once for the transpose, once for the reflection). Since $N^2$ is the size of the matrix, this is strictly optimal.
Space Complexity: O(1). The problem explicitly forbids allocating a new 2D matrix. All swaps are performed in-place.
Core Mechanism:
1. Transpose: Swap matrix[r][c] with matrix[c][r]. This flips the matrix over its main diagonal.
2. Reverse Rows: For each row, swap the elements on the left side with the elements on the right side using two pointers.

Concept Explanation

As a senior engineer, trying to write the "Four-Way Coordinate Cycle" algorithm in an interview is a recipe for off-by-one errors. It's confusing to read and fragile to write under pressure.

Instead, rely on geometric composition. Any rigid 2D rotation can be composed of reflections (flips).

The Transpose: Imagine grabbing the top-right corner and the bottom-left corner of the matrix and flipping it. The main diagonal ([0][0] to [N-1][N-1]) stays completely still. Everything else swaps across that diagonal. What used to be the first row is now the first column.
The Reflection: Look at that new first column. To achieve a 90° clockwise rotation, that column actually needs to be the last column. So, how do we push the left side to the right side? We just reverse every single row independently.

If you ever need to rotate 90° Counter-Clockwise, you do the exact same operations, just in reverse order: Reverse Rows first, then Transpose.

Diagram

This flowchart outlines the two-step geometric composition.

Loading diagram…

Study Pattern (SDE3+)

0–3 min: Immediately state the linear algebra trick: "Transpose then Reverse". Explain that while the 4-way coordinate swap exists, the Transpose+Reverse method is vastly superior for readability and maintainability.
Implementation pass: Be extremely careful with the inner loop of the Transpose phase. The col must start at row + 1. If it starts at 0, you will transpose every element twice, which puts the matrix right back where it started!
5 min extension: What if the matrix is $M \times N$ (a rectangle) instead of an $N \times N$ square? Explain that an in-place transpose is physically impossible because the dimensions change (a $2 \times 3$ becomes a $3 \times 2$). You would be forced to allocate a new matrix, breaking the $O(1)$ space constraint.

Approaches

Brute force (Allocate New Matrix) — Create res[N][N]. Map matrix[r][c] to res[c][N-1-r]. Time: $O(N^2)$, Space: $O(N^2)$. Fails problem constraints.
Four-Way Cycle — Rotate four cells at a time, moving inward layer by layer. Time: $O(N^2)$, Space: $O(1)$. Optimal bounds, but highly prone to index bounds bugs.
Transpose + Reverse — Time: $O(N^2)$, Space: $O(1)$. (Pick this)

Optimal Solution

Go

func rotate(matrix [][]int) {
	n := len(matrix)

	// Phase 1: Transpose the matrix
	// Swap matrix[r][c] with matrix[c][r]
	for r := 0; r < n; r++ {
		// Critical: c starts at r + 1 to only visit the top-right triangle
		for c := r + 1; c < n; c++ {
			matrix[r][c], matrix[c][r] = matrix[c][r], matrix[r][c]
		}
	}

	// Phase 2: Reverse every row
	for r := 0; r < n; r++ {
		left := 0
		right := n - 1
		for left < right {
			matrix[r][left], matrix[r][right] = matrix[r][right], matrix[r][left]
			left++
			right--
		}
	}
}

JavaScript

function rotate(matrix) {
	const n = matrix.length;

	// Phase 1: Transpose
	for (let r = 0; r < n; r++) {
		// Critical: c starts at r + 1 to avoid double-swapping
		for (let c = r + 1; c < n; c++) {
			let temp = matrix[r][c];
			matrix[r][c] = matrix[c][r];
			matrix[c][r] = temp;
		}
	}

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

			left++;
			right--;
		}
	}
}

Walkthrough

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

Initial State:

1 2 3
4 5 6
7 8 9

Phase 1: Transpose Only swap elements where col > row.

r=0, c=1: Swap 2 and 4
r=0, c=2: Swap 3 and 7
r=1, c=2: Swap 6 and 8

1 4 7
2 5 8
3 6 9

Phase 2: Reverse Rows Swap left and right ends of each row.

Row 0: Swap 1 and 7
Row 1: Swap 2 and 8
Row 2: Swap 3 and 9

7 4 1
8 5 2
9 6 3

Output is the 90° rotated matrix.

Edge Cases

n == 1. (Both loops terminate immediately, no-op, which is correct).
The algorithm works identically for both odd and even values of n.

Pitfalls

Starting the inner loop of the transpose at c = 0 instead of c = r + 1. If you do this, you will swap (0,1) with (1,0), and then later swap (1,0) with (0,1). The matrix will end up exactly as it started.
Trying to use [a, b] = [b, a] array destructuring syntax in JS for matrix swaps. While it works, it creates temporary arrays under the hood, violating strict $O(1)$ space constraints and massively slowing down execution. Standard temp variables are preferred.

Mind-Map Tags

#matrix #linear-algebra #transpose #reverse #in-place