Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement 
1.2.
Sample Examples
2.
Transpose and Reverse Column Approach 
2.1.
Algorithm
2.2.
Implementation
2.2.1.
Time Complexity
2.2.2.
Space Complexity
3.
Frequently Asked Questions
3.1.
What is a transpose of a matrix?
3.2.
Why is the time complexity of the program rotate a matrix O(R*C)?
3.3.
Why is the space complexity of the program rotate a matrix O(1)?
4.
Conclusion
Last Updated: Mar 27, 2024
Easy

Rotate a Matrix 90 Degrees (Without using Extra Space)

Create a resume that lands you SDE interviews at MAANG
Speaker
Anubhav Sinha
SDE-2 @
12 Jun, 2024 @ 01:30 PM

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

  1. 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.
  2. 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. 
  3. To find the transpose, swap the elements at positions (i,j) with (j, i). 
  4. Now run two loops, the outer loop from 0 to row count and the inner loop from 0 to the outer loop's index.
  5. To reverse the column of the transposed matrix, we will run two nested loops.
  6. 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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

What is a transpose of a matrix?

A matrix's transpose is found by swapping its rows for columns or columns for rows.

Why is the time complexity of the program rotate a matrix O(R*C)?

The time complexity of the program, rotate a matrix 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, the time complexity is O(n^2). In the function to find the transpose of the matrix and to reverse the column of the transpose matrix, there are nested loops; that’s why the time complexity of this approach would be O(R*C).

Why is the space complexity of the program rotate a matrix O(1)?

Because the algorithm is an in-place algorithm, the space complexity of the program, rotating a matrix is O(1).

Conclusion

This article extensively discussed the problem, rotate a matrix by 90 degrees without using extra space.
We hope this blog has helped you enhance your knowledge regarding multi-dimensional array problems. After reading about the topic, rotate a matrix by 90 degrees, are you not feeling excited to read/explore more articles on this topic? Don't worry; Coding Ninjas has you covered.

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! 

But suppose you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problems, interview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Previous article
Multiplication of two matrices
Next article
Rotate a Matrix by 180-degree
Live masterclass