Medium
You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).
You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.
Example 1:
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]
Example 2:
Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
Constraints:
n == matrix.length == matrix[i].length1 <= n <= 20-1000 <= matrix[i][j] <= 1000
In Leetcode Question, we actually rotating a matrix in clockwise direction by 90 degree.
-
Time complexity: O(n^2)
-
Space complexity: O(n^2)
Procedure
-
Taking first row, put it into last column.
-
Taking second row, put it into second last column.
-
Taking third row, put it into third last column.
// Brute Force Approach
// Time complexity --> O(n^2) and Space --> O(n^2)
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n=matrix.size();
cout<<n;
vector<vector<int>> rotate(n, vector <int> (n, 0));
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
rotate[j][n-i-1]=matrix[i][j];
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
matrix[i][j]=rotate[i][j];
}
}
}
};
-
Time complexity: O(n^2)
-
Space complexity: O(1)
Procedure
-
Firsty, Transpose the given matrix.
-
Then, Reverse every row of matrix.
-
After that, we successfully rotated the matrix clockwise.
// Optimized Approach
// Time complexity --> O(n^2) and Space --> O(1)
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n=matrix.size();
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
swap(matrix[i][j],matrix[j][i]);
}
}
for(int i=0;i<n;i++)
{
reverse(matrix[i].begin(),matrix[i].end());
}
}
};
In GFG Question, we actually rotating a matrix in anti-clockwise direction by 90 degree.
Given a square matrix of size N x N. The task is to rotate it by 90 degrees in anti-clockwise direction without using any extra space.
Example 1:
Input:
N = 3
matrix[][] = {{1, 2, 3},
{4, 5, 6}
{7, 8, 9}}
Output:
Rotated Matrix:
3 6 9
2 5 8
1 4 7
Example 2:
Input:
N = 2
matrix[][] = {{1, 2},
{3, 4}}
Output:
Rotated Matrix:
2 4
1 3
Your Task:
You don't need to read input or print anything. Complete the function rotateby90() which takes the matrix as input parameter and rotates it by 90 degrees in anti-clockwise direction without using any extra space. You have to modify the input matrix in-place.
Expected Time Complexity: O(n^2)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 100
1 <= matrix[][] <= 1000
-
Time complexity: O(n^2)
-
Space complexity: O(n^2)
Procedure
-
Taking last column, put it into first row.
-
Taking second last column, put it into second row.
-
Taking third last column, put it into third row.
// Brute Force Approach
// Time complexity --> O(n^2) and Space --> O(n^2)
class Solution
{
public:
//Function to rotate matrix anticlockwise by 90 degrees.
void rotateby90(vector<vector<int> >& matrix, int n)
{
// code here
vector<vector<int>> rotate(n, vector <int> (n, 0));
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
rotate[i][j]=matrix[j][n-i-1];
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
matrix[i][j]=rotate[i][j];
}
}
}
};
-
Time complexity: O(n^2)
-
Space complexity: O(1)
Procedure
-
Firsty, Transpose the given matrix.
-
Then, Reverse every column of matrix.
-
After that, we successfully rotated the matrix anti-clockwise.
// Optimized Approach
// Time complexity --> O(n^2) and Space --> O(1)
class Solution
{
public:
//Function to rotate matrix anticlockwise by 90 degrees.
void rotateby90(vector<vector<int> >& matrix, int n)
{
// code here
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
swap(matrix[i][j],matrix[j][i]);
}
}
for(int i=0;i<n;i++)
{
int start=0,end=n-1;
while(start<end)
{
swap(matrix[start][i],matrix[end][i]);
start++;
end--;
}
}
}
};
-
Solution Link