LeetCode 48: Rotate Image - Optimal C++ Solution & Explanation
Problem Statement
You are given an n x n 2D matrix representing an image. Rotate the image 90 degrees (clockwise)in-place.
Example:
Input:
[
[1,2,3],
[4,5,6],
[7,8,9]
]
Output:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
Constraints:
n == matrix.length == matrix[i].length
1 <= n <= 20
-1000 <= matrix[i][j] <= 1000
Optimal Approach: Transpose & Reverse
Explanation:
Transpose the matrix: Swap matrix[i][j] with matrix[j][i] for i < j.
Reverse each row: Swap elements symmetrically along the middle column.
C++ Implementation (LeetCode-Compatible)
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
// Transpose the matrix
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
swap(matrix[i][j], matrix[j][i]);
}
}
// Reverse each row
for (int i = 0; i < n; i++) {
reverse(matrix[i].begin(), matrix[i].end());
}
}
};
Step-by-Step Explanation
Transpose the matrix:
Swap elements across the diagonal (matrix[i][j] <-> matrix[j][i]).
Reverse each row:
Reverse every row to complete the 90-degree rotation.
Dry Run Example:
Input:
[
[1,2,3],
[4,5,6],
[7,8,9]
]
Execution Steps:
Step
Matrix State
Transpose
[ [1,4,7], [2,5,8], [3,6,9] ]
Reverse Rows
[ [7,4,1], [8,5,2], [9,6,3] ]
Alternative Approaches & Why Not?
Approach
Time Complexity
Space Complexity
Why Not Optimal?
Brute Force (New Matrix)
O(N^2)
O(N^2)
Extra space used
Layer-wise Rotation
O(N^2)
O(1)
More swaps, less intuitive
Layer-wise Rotation (Alternative)
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
for (int layer = 0; layer < n / 2; layer++) {
int first = layer, last = n - 1 - layer;
for (int i = first; i < last; i++) {
int offset = i - first;
int top = matrix[first][i];
matrix[first][i] = matrix[last - offset][first];
matrix[last - offset][first] = matrix[last][last - offset];
matrix[last][last - offset] = matrix[i][last];
matrix[i][last] = top;
}
}
}
};
Why is Layer-wise Rotation Less Optimal?
More swap operations than transpose + reverse.
Harder to understand and implement correctly.
Best Solution & Why?
Approach
Time Complexity
Space Complexity
Best Choice?
Transpose & Reverse
O(N^2)
O(1)
✅ Best (intuitive & efficient)
Layer-wise Rotation
O(N^2)
O(1)
❌ More swaps
Brute Force (Extra Matrix)
O(N^2)
O(N^2)
❌ Uses extra memory
Why is Transpose & Reverse Best?
Linear Time Complexity (O(N^2)) ✅
Constant Space (O(1)) ✅
Simpler & More Intuitive ✅
Conclusion
Best Solution:Transpose & Reverse.
Why? Efficient O(N^2) time, O(1) space.
Alternative Solutions: Layer-wise swaps (more steps), Brute force (extra space).
