Rotate Image — Layered Matrix Transpose and Reverse
Transpose the square matrix then reverse each row to achieve an in-place 90° rotation.
Problem Statement
Rotate an n × n matrix by 90 degrees clockwise in-place without allocating another matrix.
Why This Problem Matters
- Tests spatial reasoning with in-place data transformations.
- Highlights how composing simple operations (transpose + reverse) yields complex rotations.
- A favourite array manipulation problem that leads to deeper matrix traversal questions.
Thought Process
Recognise symmetry
For square matrices, transposition swaps (i, j) with (j, i), bringing elements into the correct row for the rotation.
Finish with row reversal
After transposing, each row is in reverse order relative to the target orientation; reversing puts elements into final positions.
Ensure in-place swaps avoid double-work
Only process the upper triangle when transposing to avoid swapping elements twice.
Step-by-Step Reasoning
- Transpose: for i < n, for j = i + 1..n-1 swap matrix[i][j] with matrix[j][i].
- Reverse each row individually.
- Return the matrix; modifications are in-place.
Dry Run
matrix = [[1,2,3],[4,5,6],[7,8,9]]
Transpose to [[1,4,7],[2,5,8],[3,6,9]] then reverse rows → [[7,4,1],[8,5,2],[9,6,3]].
Check corners
Element at (0,0) ends up at (0,n-1) after transpose + reverse.
Complexity Analysis
Time
O(n^2)
Space
O(1)
Why
Every element is swapped at most once; no additional storage beyond a temp variable is needed.
Annotated Solution
public class RotateImage {
public void rotate(int[][] matrix) {
int n = matrix.length;
for (int i = 0; i < n; i += 1) {
for (int j = i + 1; j < n; j += 1) {
int tmp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = tmp;
}
}
for (int[] row : matrix) {
int left = 0;
int right = n - 1;
while (left < right) {
int tmp = row[left];
row[left] = row[right];
row[right] = tmp;
left += 1;
right -= 1;
}
}
}
}Transpose swaps across the diagonal once, and reversing rows completes the rotation without auxiliary arrays.
Common Pitfalls
- Reversing columns instead of rows produces a counter-clockwise rotation.
- Swapping across the full matrix during transpose reverts elements to original positions.
- Applying the operations in the wrong order fails—reverse must follow transpose for clockwise rotation.
Follow-Up Questions
- How would you rotate counter-clockwise? (Transpose then reverse columns.)
- Can you generalise to 180° or 270° without repeating logic? (Compose operations appropriately.)