Rotate Image
Asked at Apple, Oracle
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| Apple | Medium | View all Apple questions → |
| Oracle | Medium | View all Oracle 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.
Visual walkthrough for [[1,2,3],[4,5,6],[7,8,9]]:
- Original:
1 2 3
4 5 6
7 8 9
- Transpose (swap i,j with j,i):
1 4 7
2 5 8
3 6 9
- Reverse each row:
7 4 1
8 5 2
9 6 3
This is the 90-degree clockwise rotation.
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.
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
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()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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Rotate Image?
Rotate Image is asked at Apple, Oracle. 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.