Question : A n*n matrix is given to you .You need to rotate the matrix in clockwise direction by 90 degree.
Input:
1 2 3
4 5 6
7 8 9
Output:
7 4 1
8 5 2
9 6 3
Brute Solution :
If you carefully obeserve the input example , first row of input matrix i.e. [1 2 3] becomes last coloumn of output matrix .
So basically what you can do is allocate an one new matrix , take the first row of input matrix and put it into the new matrix .Take the second row ,put it into the second last coloumn and so on .. , then nth row in nth last coloumn.
The new matrix you get this way is the rotated matrix of input matrix by 90 degree.
Time complexity : O(n^2)
Space complexity : O(n^2)
Space Optimal Solution :
In place solution : So when we are going to solve it as inplace solution first we will be taking the transpose of the matrix.Transpose is basically where coloumns become row and vice-versa.
So after taking transpose of the input matrix , the new matrix will look like :
1 4 7
2 5 8
3 6 9
Once you have the transpose matrix ,you can see every row is reverse of the matrix you needed as output.
So basically you can reverse each row of the transpose matrix and can get your desired matrix.
Steps to perform rotate by 90 degree of matrix :
a)Transpose of matrix
b)Reverse every Row
Code : C++ function to do the rotation by 90 degree:void rotate(vector<vector<int>>& matrix){ for(int i=0;i<matrix.size();i++) { for(int j=0;j<i;j++){ swap(matrix[i][j],matrix[j][i]); } } for(int j=0;j<matrix.size();j++) { reverse(matrix[j].begin(),matrix[j].end()); } }
Time complexity : O(n^2) Space Complexity : O(1)
Leave a Reply