Rotate Image 🧠
LeetCode Link: Rotate Image
Difficulty: Medium
Problem Explanation 📝
Problem: LeetCode 48 - Rotate Image
Description: You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).
Intuition: To rotate the image by 90 degrees clockwise, we can perform two steps:
- Transpose the matrix (rows become columns, and vice versa).
- Reverse each row of the transposed matrix.
Approach:
- Transpose the matrix in-place:
- Iterate over the upper triangle of the matrix (i.e., elements above the main diagonal).
- Swap the element at matrix[i][j] with matrix[j][i].
- Reverse each row of the transposed matrix:
- For each row, use two pointers (start and end) and swap the elements until they meet in the middle.
⌛ Time Complexity: The time complexity of this approach is O(n^2), where n is the number of rows (or columns) in the matrix.
💾 Space Complexity: The space complexity is O(1) as we are performing the rotation in-place without using any additional space.
Solutions 💡
Cpp 💻
class Solution {
public:
void rotate(vector<vector<int>> &matrix) {
int n = matrix.size();
// Step 1: Transpose the matrix
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
swap(matrix[i][j], matrix[j][i]);
}
}
// Step 2: Reverse each row of the transposed matrix
for (int i = 0; i < n; i++) {
int start = 0;
int end = n - 1;
while (start < end) {
swap(matrix[i][start], matrix[i][end]);
start++;
end--;
}
}
}
};
Python 🐍
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
n = len(matrix)
# Transpose the matrix
for i in range(n):
for j in range(i, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
# Reverse each row
for i in range(n):
matrix[i].reverse()