We’ll understand rotating elements of a matrix by 90 degrees, without using extra space and write the program to implement the same.
Directly placing the elements of a matrix row by row in a temporary matrix is a reasonable solution, but the space complexity doubles in that case, when we have large sets of data, along with space complexity also becomes a concern, so here we’ll try to understand a solution which reduces the space complexity while rotating a matrix by 90 degrees.
Table of Contents
Approach to the Algorithm
We will increase the number of steps, it sounds counter-intuitive at first, but it does help eliminate the temporary matrix out of the picture, imagine the following process.
1. Given Matrix
2. Transpose step
3. Reversing rows
Instead of rotating the matrix, first, take the transpose of the matrix in place. You can learn how to take the transpose of a matrix in place, here. Then after the transpose, invert the order of the rows and we get a matrix that’s rotated 90 degrees.
Breaking the code into steps:
In our rotate function, we’ll be carrying out two linear transformation one by one. So there will be 2 separate nested loops.
- Transpose loop
- As we know from a transpose algorithm, we have to swap elements for the whole upper/lower triangular matrix, and the diagonal elements remain the same, thus we perform the following operation.
- Swap mat[i,j] with mat[j,i]
- Reversing matrix
- Now similarly we have to reverse the rows of the matrix, but we only have to traverse to the center row and stop, as one swap operation results in 2 rows in right place.
- Swap mat[low,i] with mat[high,i]
Now that these basics of the algorithm is clear, take a look at the following code and hopefully it will click into place.
Program for rotating the matrix by 90 degrees
#include<stdio.h>
#include<bits/stdc++.h>
void rotate90(int **arr, int n) //function declaration, pass by reference
{
for(int i=0;i<n;i++) //outer loop begins, transpose of the matrix
{
for(int j=i+1;j<n;j++)//1 inner loop, initializing j to traverse upper triangle
swap(arr[i][j],arr[j][i]);
}
for( int i=0; i<n ; i++) //2nd outer loop, reversing the rows top to bottom
{
int low=0, high=i-1; //Initializing variables for inner loop
while(low<high) //condition to stop at the middle of the matrix
{
swap(arr[low][i],arr[high][i]);
low++;
high--;
}
}
}
void printarr(int **arr, int n) //print function to display the output
{
cout<<endl;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cout<<arr[i][j]<<" ";
}
cout<<endl;
}
}
int main(void) {
int **arr;
int n=3;
arr=new int *[n];
cout<<"The Original matrix is: "<<endl;
for(int i=0;i<n;i++){ //initialization of matrix
arr[i]=new int[n];
for(int j=0;j<n;j++){
arr[i][j]=rand() % 100 + 1;
cout<<arr[i][j]<<" ";
}
cout<<endl;
}
rotate90(arr,n); //calling the rotate funciton
cout<<"90 degree Rotated Matrix";
printarr(arr,n); // output
return 0;
}
Output:
Original matrix:
84 87 78
16 94 36
87 93 50
90 degree Rotated Matrix:
84 16 93
87 94 87
78 36 50
Why did we increase loops?
We know time complexity increases as we increase our loops, so it’s always advised to reduce steps can you think of why didn’t we directly swap the elements? Swapping mat[i,j] with mat[n-1-j, i] actually functions well, the problem is with the execution of the swap function, one swap results in 2 numbers in right place, so we have to execute the function on only half the matrix, and in transpose and reverse, we know a neutral plane about which the transformation takes place diagonal and the center row respectively. Thus we break down the complex function into smaller linear transformations which reduces our space complexity significantly.
Time Complexity of the program
As we saw the traversal of the matrix is carried out twice and is half the number of elements for each. Thus the time complexity of O(R*C). Discuss in the comments whether the time complexity can be further reduced.
Related:
Further you can look how to spirally traverse a matrix and print the results in a line here.