Introduction
Rotating a matrix by 90 degrees is a multi-dimensional array problem. It had been recently asked in the Aruba HPE intern round for the role of software developer intern. Alongside it is one of those problems that checks an individual's critical thinking by analyzing the most fundamental approach and the basic simple mathematics of the programmer.
In this article, we’ll use a reverse column and transpose matrix approach to solve this programming problem.
Must Read, Array Implementation of Queue and Rabin Karp Algorithm
Problem Statement
Given a square matrix, the task is to turn it 90 degrees anti-clockwise without using extra space.
Sample Examples
Example 1:
Input
Output
Rotated the input matrix by 90 degrees.
Example 2:
Input
Output
Rotated the input matrix by 90 degrees.
Transpose and Reverse Column Approach
As we are doing anti-clockwise rotation by taking transpose and reversing the column, we will understand this process with help of an example.
Algorithm
- There are two tasks to complete in order to rotate the given matrix. The first step is to find the transpose of the matrix, and the second step is to reverse the columns anti-clockwise without using any extra space.
- A matrix transpose occurs when the matrix is rotated across its diagonal, that is, the row index of an element will become its column index and vice versa.
- To find the transpose, swap the elements at positions (i,j) with (j, i).
- Now run two loops, the outer loop from 0 to row count and the inner loop from 0 to the outer loop's index.
- To reverse the column of the transposed matrix, we will run two nested loops.
- The outer loop from 0 to column count and the inner loop from 0 to row count/2, swapping elements at (i, j) with (i, row[count-1-j]), where i and j are inner and outer loop indices.
Implementation
#include <bits/stdc++.h>
#include <cmath>
#include <regex>
using namespace std;
//Function to reverse the column of matrix
void reverseColumns(vector<vector<int>> &matrix)
{
for (int i = 0; i < 3; i++)
for (int j = 0, k = 2; j < k; j++, k--)
swap(matrix[j][i], matrix[k][i]);
}
// Function for do transpose of matrix
void transposematrix(vector<vector<int>> &matrix)
{
for (int i = 0; i < 3; i++)
for (int j = i; j < 3; j++)
swap(matrix[i][j], matrix[j][i]);
}
int main()
{
vector<vector<int>> matrix{
{ 11, 12, 13 },
{ 14, 15, 16 },
{ 17, 18, 19 }
};
transposematrix(matrix);
reverseColumns(matrix);
for(int i=0;i<3;i++)
{
for(int j=0;j<3;j++)
{
cout<<matrix[i][j]<<" ";
}
cout<<"\n";
}
return 0;
}
Output
Time Complexity
The time complexity of this approach is O(R*C), where R is the number of rows and C is the number of columns, for the above program and every square matrix( N X N), the time complexity is O(N^2).
Space Complexity
The space complexity of this program, rotating a matrix will be O(1) as we are not using any extra space.