Problem Description
đź”— Link to Question: https://leetcode.com/problems/rotate-image/editorial/
You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).
Observation 🔎
Naive Approach
- Observe that the ith col turns into ith row in reversed form
- Create a New Matrix and use it to update the original matrix.
Code
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n=matrix.size();
auto v = matrix;
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
matrix[j][n-i-1] = v[i][j];
}
}
}
};
Complexity Analysis
- Time:
- Space:
Using Matrix Operations
- Transpose the Matrix
- Now columns ↔ rows are interchanged Or we’ve performed a reverse operation around the diagonals.
- Reverse the Rows.
We are just exploiting the fact that columns are turned into rows in reversed fashion.
Code
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n=matrix.size();
//Transpose the Matrix
transpose(matrix);
//Reverse the rows
for(int i=0; i<n; i++)
{
reverse(matrix[i].begin(), matrix[i].end());
}
}
//Reverse around the Diagonal
void transpose(vector<vector<int>>& matrix)
{
int n=matrix.size();
for(int i=0; i<n; i++)
{
//[0..i-1] columns are correctly modified
for(int j=i; j<n; j++)
{
swap(matrix[i][j], matrix[j][i]);
}
//After modifying ith row, ith col is also correctly modified
}
}
};
Complexity Analysis
- Time:
- Space:
Top comments (0)