Rotate Image

Problem in Plain English

Rotate an n x n matrix 90 degrees clockwise in place, rewriting the input directly instead of allocating a second matrix.

Problem Statement

You are given an n x n 2D matrix picturing an image. Rotate the image 90 degrees clockwise.

The rotation must happen in place: modify the input matrix directly without allocating another 2D matrix for the result.

Constraints

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

Examples

Example 1

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

Each row becomes a column read bottom to top: the top row [1, 2, 3] becomes the right column.

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]]

The old left column [5, 2, 13, 15] becomes the new top row [15, 13, 2, 5]. The inner 2 by 2 block also rotates: [[4, 8], [3, 6]] becomes [[3, 4], [6, 8]], so rotating just the outer border would be wrong.

Example 3

Input: matrix = [[-1000]]
Output: [[-1000]]

The only cell is also the center. Both diagonal swapping and row reversal have no pairs to process, so its value and position stay unchanged.

Intuition

Follow positions rather than values: a clockwise quarter-turn sends row r, column c to row c, column n - 1 - r. In Example 1, the top-left 1 becomes the top-right 1, and the bottom-left 7 becomes the top-left 7. Directly overwriting destinations would destroy values still needed elsewhere. A spare matrix illustrates the mapping, but violates the storage requirement. Instead, swap across the main diagonal and then reverse each row; these two reflections achieve the same movement without losing a value.

Approaches

Copy to New Matrix

Solution Details

Reveal Copy to New Matrix: intuition, complexity, and code

Intuition

Write each source cell into its clockwise destination in a separate matrix, then copy the result back into the existing rows. The extra storage prevents unread source values from being overwritten. This is a teaching baseline: it computes and mutates the correct result, but allocating a second matrix violates the stated in-place restriction.

Step-by-Step Logic

Let n be the number of rows and allocate n distinct result rows of length n. Example 1 has n = 3; all nine temporary cells initially contain zero.
Scan every source row r and column c. Assign its value to result[c][n - 1 - r]; in Example 1, (0, 0) = 1 moves to (0, 2), while (0, 1) = 2 moves to (1, 2).
Finish a source row before advancing r. Example 1 first fills the right column [1, 2, 3], then the middle column [4, 5, 6], then the left column [7, 8, 9].
Once every source has been read, copy all n squared result cells back into matrix, cell by cell. Example 1 ends as [[7, 4, 1], [8, 5, 2], [9, 6, 3]] without replacing any row.
Use the second approach for the required constant-space solution; this baseline spends a second matrix even though it updates the caller input.

Why It Works

The destination of source (r, c) is (c, n - 1 - r). This mapping is one-to-one: a destination (a, b) has exactly the source (n - 1 - b, a), so no cell is omitted or overwritten by another source. The original matrix stays unchanged during the first pass, preserving every source value. The second pass copies every completed destination back into its corresponding input cell and keeps the original row objects. Value correctness does not make this baseline satisfy the no-extra-matrix constraint.

Dry Run

Copy to New Matrix: variable states at each step
r, c / phase	value	destination	result after	matrix after
allocate	—	—	[[0,0,0],[0,0,0],[0,0,0]]	input unchanged
0, 0	1	0, 2	[[0,0,1],[0,0,0],[0,0,0]]	input unchanged
0, 1	2	1, 2	[[0,0,1],[0,0,2],[0,0,0]]	input unchanged
0, 2	3	2, 2	[[0,0,1],[0,0,2],[0,0,3]]	input unchanged
1, 0	4	0, 1	[[0,4,1],[0,0,2],[0,0,3]]	input unchanged
1, 1	5	1, 1	[[0,4,1],[0,5,2],[0,0,3]]	input unchanged
1, 2	6	2, 1	[[0,4,1],[0,5,2],[0,6,3]]	input unchanged
2, 0	7	0, 0	[[7,4,1],[0,5,2],[0,6,3]]	input unchanged
2, 1	8	1, 0	[[7,4,1],[8,5,2],[0,6,3]]	input unchanged
2, 2	9	2, 0	[[7,4,1],[8,5,2],[9,6,3]]	input unchanged
copy 0, 0	7	0, 0	[[7,4,1],[8,5,2],[9,6,3]]	[[7,2,3],[4,5,6],[7,8,9]]
copy 0, 1	4	0, 1	[[7,4,1],[8,5,2],[9,6,3]]	[[7,4,3],[4,5,6],[7,8,9]]
copy 0, 2	1	0, 2	[[7,4,1],[8,5,2],[9,6,3]]	[[7,4,1],[4,5,6],[7,8,9]]
copy 1, 0	8	1, 0	[[7,4,1],[8,5,2],[9,6,3]]	[[7,4,1],[8,5,6],[7,8,9]]
copy 1, 1	5	1, 1	[[7,4,1],[8,5,2],[9,6,3]]	[[7,4,1],[8,5,6],[7,8,9]]
copy 1, 2	2	1, 2	[[7,4,1],[8,5,2],[9,6,3]]	[[7,4,1],[8,5,2],[7,8,9]]
copy 2, 0	9	2, 0	[[7,4,1],[8,5,2],[9,6,3]]	[[7,4,1],[8,5,2],[9,8,9]]
copy 2, 1	6	2, 1	[[7,4,1],[8,5,2],[9,6,3]]	[[7,4,1],[8,5,2],[9,6,9]]
copy 2, 2	3	2, 2	[[7,4,1],[8,5,2],[9,6,3]]	[[7,4,1],[8,5,2],[9,6,3]]
finish	—	—	[[7,4,1],[8,5,2],[9,6,3]]	[[7,4,1],[8,5,2],[9,6,3]]

Complexity Analysis

Time Complexity

O(n^2)

Space Complexity

O(n^2)

For an n by n matrix, allocating and initializing the result, filling it, and copying it back each cost O(n squared) time. The result holds n squared cells plus n row objects/references, so auxiliary space is O(n squared); scalar indices use constant additional space. It preserves input and row identity, but does not meet the prohibition on a second matrix.

Code

Solution.java

1class Solution {2    public void rotate(int[][] matrix) {3        int n = matrix.length;4        int[][] res = new int[n][n];5        // Read all sources before writing back; (r, c) turns into (c, n - 1 - r).6        for (int r = 0; r < n; r++) {7            for (int c = 0; c < n; c++) {8                res[c][n - 1 - r] = matrix[r][c];9            }10        }11        for (int r = 0; r < n; r++) {12            for (int c = 0; c < n; c++) {13                matrix[r][c] = res[r][c];14            }15        }16    }17}

Hints

Hint 1

Follow one cell: 1 starts at the top-left and must end at the top-right, so rows become columns.

Hint 2

Try transposing first (swap matrix[i][j] with matrix[j][i] for j above the diagonal) and look at what each row needs next.

Hint 3

After the transpose, reversing every row left to right completes the clockwise turn with no extra matrix.

Edge Cases

A 1 by 1 matrix such as [[-1000]] has no swap pairs and remains unchanged.
A 2 by 2 matrix [[1, 2], [3, 4]] becomes [[3, 1], [4, 2]]: one transpose swap and one reversal swap per row.
Odd sizes keep the central cell fixed; other cells in its row and column still move.
Even sizes have no single central cell; inner layers must rotate as well as the border, as in Example 2.
Repeated values, zeros, and values -1000 or 1000 are handled by position, not by comparison.

Common Mistakes and Interview Tips

Transposing with j starting at 0 swaps every off-diagonal pair twice. Start at i + 1.
Overwriting matrix[c][n - 1 - r] directly during a source scan destroys unread values; use swaps for the actual in-place solution.
Reversing columns after transposition produces a counterclockwise rotation. Reverse each row for clockwise movement.
Reversing through the entire row swaps each pair twice. Stop before half the length.
Rebinding matrix to a new result only changes a local variable in Python/JavaScript; it does not update the caller matrix. Replacing rows also loses row identity.
The copy baseline shows the coordinate mapping, but a second matrix still violates the stated restriction even if copied back. In an interview, derive the two reflections and explain why each pair is visited once.

Key Takeaway

A rotation can factor into simpler reflections: transpose plus row reversal turns clockwise, and each factor needs only pairwise swaps.