🎨Now live: Try our Free AI Image Generation Feature

Intuition
To rotate the matrix 90 degrees clockwise, we can break down the problem into two simpler steps:
- Reverse the rows of the matrix (vertical flip).
- Transpose the matrix (convert rows to columns).
Approach
- Vertical Flip:
- Initialize
top
to the first row (index 0) andbottom
to the last row (indexedgeLength - 1
). - Swap the elements of thetop
row with thebottom
row for each column. - Movetop
down andbottom
up until they meet. - Transpose the Matrix:
- Iterate over each element above the main diagonal.
- Swap the element at position
(row, col)
with the element at position(col, row)
.
Complexity
Time Complexity:
O(n^2)
- We iterate over all elements in the matrix twice: once for the vertical flip and once for the transpose. Therefore, the time complexity is O(n^2).
Space Complexity:
O(1)
- We perform the operations in-place without using any extra space apart from a few temporary variables for swapping. Therefore, the space complexity is O(1).
Code
C++
class Solution {
public:
void rotate(vector>& matrix) {
int edgeLength = matrix.size();
int top = 0;
int bottom = edgeLength - 1;
while (top < bottom) {
for (int col = 0; col < edgeLength; ++col) {
int temp = matrix[top][col];
matrix[top][col] = matrix[bottom][col];
matrix[bottom][col] = temp;
}
top++;
bottom--;
}
for (int row = 0; row < edgeLength; ++row) {
for (int col = row + 1; col < edgeLength; ++col) {
int temp = matrix[row][col];
matrix[row][col] = matrix[col][row];
matrix[col][row] = temp;
}
}
}
};
Python
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
edgeLength = len(matrix)
top = 0
bottom = edgeLength - 1
while top < bottom:
for col in range(edgeLength):
matrix[top][col], matrix[bottom][col] = matrix[bottom][col], matrix[top][col]
top += 1
bottom -= 1
for row in range(edgeLength):
for col in range(row + 1, edgeLength):
matrix[row][col], matrix[col][row] = matrix[col][row], matrix[row][col]
Java
class Solution {
public void rotate(int[][] matrix) {
int edgeLength = matrix.length;
int top = 0;
int bottom = edgeLength - 1;
while (top < bottom) {
for (int col = 0; col < edgeLength; col++) {
int temp = matrix[top][col];
matrix[top][col] = matrix[bottom][col];
matrix[bottom][col] = temp;}
top++;
bottom--;}
for (int row = 0; row < edgeLength; row++) {
for (int col = row + 1; col < edgeLength; col++) {
int temp = matrix[row][col];
matrix[row][col] = matrix[col][row];
matrix[col][row] = temp;
}
}
}
}
JavaScript
var rotate = function(matrix) {
const edgeLength = matrix.length;
let top = 0;
let bottom = edgeLength - 1;
while (top < bottom) {
for (let col = 0; col < edgeLength; col++) {
let temp = matrix[top][col];
matrix[top][col] = matrix[bottom][col];
matrix[bottom][col] = temp; }
top++;
bottom--;}
for (let row = 0; row < edgeLength; row++) {
for (let col = row + 1; col < edgeLength; col++) {
let temp = matrix[row][col];
matrix[row][col] = matrix[col][row];
matrix[col][row] = temp;
}
}
};