Approach Summary
Two-step in-place: first transpose (swap [i][j] and [j][i]), then mirror horizontally (reverse each row).
Practice Mode
2 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Auxiliary Matrix Copy | O(N^2) | O(N^2) | Creates a duplicate matrix and maps each element (i, j) to (j, n - 1 - i) before copying back. |
| 2 Approach 2: In-Place Transpose and Reflect (Optimal) | O(N^2) | O(1) | First transposes matrix along the main diagonal, then reflects (reverses) each row horizontally in O(1) auxiliary space. |
Step 1: Baseline
Approach 1: Auxiliary Matrix Copy
Time: O(N^2)
Space: O(N^2)
1. Allocate a new matrix `clone` of identical size N x N. 2. For each cell (i, j), assign `clone[j][n - 1 - i] = matrix[i][j]`. 3. Copy `clone` back into `matrix`. 4. Simple to reason about, but does not satisfy in-place constant space requirements.
Approach 1: Auxiliary Matrix Copy Implementation
Approach 1: Auxiliary Matrix Copy
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
int[][] clone = new int[n][n];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) clone[i][j] = matrix[i][j];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) matrix[j][n - 1 - i] = clone[i][j];
}
}class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
auto clone = matrix;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) matrix[j][n - 1 - i] = clone[i][j];
}
};class Solution:
def rotate(self, matrix: list[list[int]]) -> None:
n = len(matrix)
clone = [[matrix[i][j] for j in range(n)] for i in range(n)]
for i in range(n):
for j in range(n):
matrix[j][n - 1 - i] = clone[i][j]var rotate = function(matrix) {
const n = matrix.length;
const clone = matrix.map(row => [...row]);
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
matrix[j][n - 1 - i] = clone[i][j];
}
}
}; Step 2: Most Optimized
Approach 2: In-Place Transpose and Reflect (Optimal)
Time: O(N^2)
Space: O(1)
1. Transpose: For `i` from 0 to N-1 and `j` from `i` to N-1, swap `matrix[i][j]` and `matrix[j][i]`. 2. Reflect: For each row `i`, use two pointers `low = 0` and `high = N - 1` to swap `matrix[i][low]` and `matrix[i][high]` while `low < high`. 3. The combination of transposing and row reversal produces the exact 90-degree clockwise rotation. 4. Requires 0 auxiliary heap allocations.
Approach 2: In-Place Transpose and Reflect (Optimal) Implementation
Approach 2: In-Place Transpose and Reflect (Optimal)
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n / 2; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[i][n - 1 - j];
matrix[i][n - 1 - j] = temp;
}
}
}
}class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
swap(matrix[i][j], matrix[j][i]);
}
}
for (int i = 0; i < n; i++) {
reverse(matrix[i].begin(), matrix[i].end());
}
}
};class Solution:
def rotate(self, matrix: list[list[int]]) -> None:
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 i in range(n):
matrix[i].reverse()var rotate = function(matrix) {
const n = matrix.length;
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
[matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
}
}
for (let i = 0; i < n; i++) {
matrix[i].reverse();
}
};Edge Cases to Watch
- 1x1 matrix [[1]] — transposing and reversing has no effect, returns [[1]]
- 2x2 matrix [[1, 2], [3, 4]] — transposes to [[1, 3], [2, 4]], reverses to [[3, 1], [4, 2]]
- Negative values and duplicate numbers — swap operations preserve value integrity regardless of sign or magnitude
Algorithmic Pattern
View Pattern Guide →
Master the Matrix Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Matrix pattern.
How to Recognize This Pattern
- Rotate matrix 90° clockwise in-place
- Transpose + mirror
Complexity Analysis
Time Complexity
O(n²)
Space Complexity
O(1)
Tags
Array Matrix Math
Frequently Asked Questions
What is the optimal time and space complexity for Rotate Image?
The optimal solution for Rotate Image achieves O(n²) runtime complexity and requires O(1) auxiliary space. Time Complexity is O(N^2) where N is the dimension of the matrix. Transposing inspects N*(N - 1)/2 elements, and horizontal reversal flips N/2 elements across N rows (N^2 / 2 swaps). Total operations are proportional to N^2. Space Complexity is O(1) auxiliary space because all swaps are performed in-place using a single temporary variable.
How do I identify that Rotate Image requires the Matrix pattern?
In technical interviews, look for key problem signals: Rotate matrix 90° clockwise in-place; Transpose + mirror. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Matrix strategy.
What critical edge cases must be handled in Rotate Image?
Essential edge cases to verify include: 1x1 matrix [[1]] — transposing and reversing has no effect, returns [[1]]; 2x2 matrix [[1, 2], [3, 4]] — transposes to [[1, 3], [2, 4]], reverses to [[3, 1], [4, 2]]; Negative values and duplicate numbers — swap operations preserve value integrity regardless of sign or magnitude. Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Rotate Image?
Rotate Image is a Medium-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Amazon, Microsoft, Apple.