Dare2Solve
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).
Vertical Flip:
Initialize top
to the first row (index 0) and bottom
to the last row (index edgeLength - 1
).
Swap the elements of the top
row with the bottom
row for each column.
Move top
down and bottom
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)
.
O(n^2)
O(1)
class Solution {
public:
void rotate(vector<vector<int>>& 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;
}
}
}
};
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]
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;
}
}
}
}
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;
}
}
};