48. Rotate Image
Asked at Apple, Oracle, Bloomberg, JPMorgan
Difficulty
Medium
Time
O(n^2)
Space
O(1)
Pattern
Array
Companies
4
Problem
You are given an n x n matrix of numbers. Rotate the whole matrix 90 degrees clockwise and return the rotated matrix.
The catch: you must do the rotation in-place. That means you change the given matrix directly and you are not allowed to build another n x n matrix to hold the answer.
A 90-degree clockwise turn moves the element at row i, column j to row j, column n-1-i. The first row of the input becomes the last column of the output, the last row becomes the first column, and so on.
What a 90-degree clockwise turn does
Constraints
- ●
n == matrix.length == matrix[i].length - ●
1 <= n <= 20 - ●
-1000 <= matrix[i][j] <= 1000
Examples
matrix = [[1,2,3],[4,5,6],[7,8,9]][[7,4,1],[8,5,2],[9,6,3]]matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]][[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]Asked At
4 companies| Company | Difficulty | |
|---|---|---|
| Apple | Medium | View all Apple questions → |
| Oracle | Medium | View all Oracle questions → |
| Bloomberg | Medium | View all Bloomberg questions → |
| JPMorgan | Medium | View all JPMorgan questions → |
How to Think About It
Brute force: create a new n x n matrix. For each cell (i, j), its new position after 90-degree clockwise rotation is (j, n-1-i). Copy to the new matrix, then copy back. That's O(n²) time and O(n²) space.
Better: transpose + reverse. First transpose the matrix (swap matrix[i][j] with matrix[j][i]). Then reverse each row. The result is a 90-degree clockwise rotation. Both steps are O(n²) in-place.
Why transpose + reverse works: a 90-degree clockwise rotation is equivalent to flipping along the main diagonal (transpose) and then flipping horizontally (reverse rows). Think of it as two reflections.
Alternative: layer-by-layer rotation. For each layer from outer to inner, rotate four cells at a time. For cell (i, j), the four cells are: (i,j) -> (j, n-1-i) -> (n-1-i, n-1-j) -> (n-1-j, i) -> back to (i,j). Process n/2 layers.
Edge cases: n=1 (no rotation needed), n=2 (swap corners). The transpose step only iterates i from 0 to n-1, j from i+1 to n-1 to avoid double-swapping.
Optimal Approach
Step 1: Transpose the matrix. For i in 0..n-1, for j in i+1..n-1, swap matrix[i][j] with matrix[j][i].
Step 2: Reverse each row. For each row, use two pointers (left, right) and swap elements moving inward.
Walkthrough with [[1,2,3],[4,5,6],[7,8,9]]:
- Transpose: swap (0,1) with (1,0) -> 2 and 4 swap. swap (0,2) with (2,0) -> 3 and 7 swap. swap (1,2) with (2,1) -> 6 and 8 swap. Matrix becomes [[1,4,7],[2,5,8],[3,6,9]].
- Reverse row 0: [7,4,1]. Row 1: [8,5,2]. Row 2: [9,6,3].
- Result: [[7,4,1],[8,5,2],[9,6,3]].
Time: O(n²) — transpose is n*(n-1)/2 swaps, reverse is n*(n/2) swaps. Space: O(1) — in-place.
Transpose, then reverse each row
What Trips People Up in Real Interviews
Swapping (i,j) with (j,i) for ALL pairs instead of j > i. If you swap both (i,j) and (j,i), you undo the transpose. Only iterate j from i+1 to n-1 to swap each pair once.
Confusing clockwise with counter-clockwise. For counter-clockwise, transpose then reverse COLUMNS (not rows). Or reverse rows then transpose. Know which one the interviewer wants.
Trying to rotate in-place without understanding the index mapping. The key formula for 90-degree clockwise: (i,j) -> (j, n-1-i). Memorize this or derive it by tracing a corner cell.
Using extra space and claiming it's in-place. Creating a new matrix and copying back is not truly in-place. The transpose + reverse approach is O(1) extra space.
Forgetting that the matrix is square (n x n). If the interviewer gives a rectangular matrix, a 90-degree rotation changes dimensions. But LeetCode guarantees n x n here.
Solution Code
O(n^2) timedef 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()Frequently Asked Questions
What is the Rotate Image problem?
Given an n x n matrix, rotate it 90 degrees clockwise in-place. The classic approach is to first transpose the matrix, then reverse each row. This tests your ability to manipulate matrix indices without extra space.
How do you solve Rotate Image?
The optimal approach runs in O(n^2) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Rotate Image?
Rotate Image is asked at Apple, Oracle, Bloomberg, JPMorgan. It is a medium difficulty problem.
What are common mistakes on Rotate Image?
- Swapping (i,j) with (j,i) for ALL pairs instead of j > i. If you swap both (i,j) and (j,i), you undo the transpose. Only iterate j from i+1 to n-1 to swap each pair once.
- Confusing clockwise with counter-clockwise. For counter-clockwise, transpose then reverse COLUMNS (not rows). Or reverse rows then transpose. Know which one the interviewer wants.
- Trying to rotate in-place without understanding the index mapping. The key formula for 90-degree clockwise: (i,j) -> (j, n-1-i). Memorize this or derive it by tracing a corner cell.
- Using extra space and claiming it's in-place. Creating a new matrix and copying back is not truly in-place. The transpose + reverse approach is `O(1)` extra space.
- Forgetting that the matrix is square (n x n). If the interviewer gives a rectangular matrix, a 90-degree rotation changes dimensions. But LeetCode guarantees n x n here.