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.
Naive Approach (Rotated Matrix)  
2.1.
Algorithm
2.2.
Implementation in C++
2.2.1.
Time complexity 
2.2.2.
Space complexity 
3.
Swapping position approach
3.1.
Algorithm
3.2.
Implementation in C++
3.2.1.
Time complexity
3.2.2.
Space complexity 
4.
Frequently Asked Questions
4.1.
What is the disadvantage of using printing the reverse order element approach?
4.2.
Why is the time complexity of the swapping approach in this program O(R*C)?
4.3.
Why is the space complexity of the swapping approach in this program O(1)?
5.
Conclusion
Last Updated: Mar 27, 2024
Easy

Rotate a Matrix by 180-degree

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 180 degrees is a multi-dimensional array problem. It had been asked in the NVIDIA interview round for the role of software engineers/developers. Alongside it is one of those problems that checks an individual's critical thinking by analyzing the most fundamental approach of the programmer. 

In this article, we’ll use two methods to solve this problem; the first is the brute force or naive approach, and the second is by swapping positions.

Problem Statement 

Given a square matrix, the task is to turn it 180 degrees without using extra space.

Sample Examples

Example 1:

Input:

                                    

Output:  

                                  

 

Example 2:

Input:    

                           

Output: 

                           

Must Read, Array Implementation of Queue and  Rabin Karp Algorithm

Naive Approach (Rotated Matrix)  

A brute force solution to this problem could be by printing a rotated matrix.

In this approach, we’ll simply print the reverse of the matrix.

Given Matrix = 

                            

First we are rotating it by 90 degrees, the new matrix will be:

90 Degrees Rotated Matrix =

                              

When we rotate it again by 90 degrees then the matrix will become:

180 Degrees Rotated Matrix =  

                                

Algorithm

  1. In order to rotate a matrix, take the matrix as an input.
  2. Traverse the whole matrix to the end.
  3. Now start printing the matrix from the last cell to the first cell.
  4. End

Implementation in C++

#include <bits/stdc++.h>
#include<iostream>
#define N 3
using namespace std;

// Function in order to Rotate the matrix by 180 degree
void rotate(int matrix[][N])
{
//Now print from the last cell to first cell of the matrix
	for (int i = N - 1; i >= 0; i--) 
	{
		for (int j = N - 1; j >= 0; j--)
		cout<< matrix[i][j]<<" ";
		cout<<"\n";
	}
}

// Main function of the program
int main()
{
	int matrix[N][N] = 
	{
		{ 1, 2, 3 },
		{ 4, 5, 6 },
		{ 7, 8, 9 }
	};
	rotate(matrix);
	return 0;
}

 

Output :

 

Time complexity 

The time complexity of this approach is O(N*N) as we are traversing the whole matrix and printing the matrix again in the reverse order in the same loop. 

Space complexity 

The space complexity of this approach is O(1), as we are using constant 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

Swapping position approach

In the swapping position approach, we are swapping the position of the element in the first row with the elements of the last row in reverse order. Now the elements of the second row with a reverse of the second last row of the matrix and so on. For the middle row, that row itself will be printed in reverse order.

Matrix = 

                    

Swapping and reversing the first row with the last row.

Matrix = 

                     

For the middle row, that row itself will be printed in reverse order.

Matrix =

                      

Algorithm

  1. There are two tasks to complete in order to rotate the given matrix. The first step is to find the swap elements of the matrix, and the second step is to rotate the matrix without using any extra space.
  2. Now swap the elements at positions (i,j) with (j, i). 
  3. Now run two loops, the outer loop from 0 to row count and the inner loop from 0 to the outer loop's index.
  4. To rotate the matrix, if r is odd, then the middle row of the matrix is reversed. 
  5. Now swap the value of matrix array[j][i] with [rows - j - 1][cols - i - 1] for the half of the size of rows.  
  6. Now print the output.

Implementation in C++

#include <iostream>
#include<bits/stdc++.h>
#include <vector>
#include <algorithm>
#define pb push_back
#define vll vector<long long int>
using namespace std;
typedef long long int ll;

// Function to swap elements of the matrix
void do_swaps(int& a, int& b, int& c, int& d) 
	{
	  swap(a, b);
	  swap(c, d);
	}

//Function to rotate the matrix
void rotate(vector<vector<int>>& v) 
	{
    	size_t m = v.size();
    	size_t n = v[0].size();
    	for (size_t i = 0; i < m / 2; ++i)
    		{
        		for (size_t j = 0; j < n; ++j)
            	swap(v[i][j], v[m - i - 1][n - j - 1]);
    		}
    	if (m&1)
    	for (size_t i = 0; i< n/2; ++i)
        swap(v[m/2][i], v[m/2][n-i-1]);
}

//Function to print the output
void print(const vector<vector<int>>& v) 
{
	  size_t m = v.size();
	  size_t n = v[0].size();
	  for(size_t i = 0; i < m; ++i) 
	  {
    		for(size_t j = 0; j < n; ++j) 
    		{
      			cout << v[i][j] << ' ';
    		}
    		cout << '\n';
  		}
}

// Main function of the program
int main() 
{
	  vector<vector<int>> m{{1,2,3}, {4,5,6}, {7,8,9}, {1, 2, 3}};
	  cout << "Before: \n";
	  print(m);
	  rotate(m);
	  cout << "\nAfter: \n";
	  print(m);
}

 

Output:

 

Time complexity

The time complexity of this approach is O(R*C). As we are rotating and swapping the matrix in the same loop, here, the time complexity of rotating is O(R), and that of swapping is O(C).

Space complexity 

The space complexity of this approach is O(1), as we are using constant extra space.

Frequently Asked Questions

What is the disadvantage of using printing the reverse order element approach?

When we rotate a matrix by printing the array in reverse order, we are traversing the whole matrix and printing the matrix again in the reverse order in the same loop. That means two nested loops have time complexities of O(N) each, resulting in the time complexity of the whole as O(N*N), but the space complexity of the program is O(n), i.e., the program is not ‘in place’, it is taking some extra space.

Why is the time complexity of the swapping approach in this program O(R*C)?

As we are rotating and swapping the matrix in the same loop, here, the time complexity of rotating is O(R), and that of swapping is O(C).

Why is the space complexity of the swapping approach in this program O(1)?

Because the algorithm is an in-place algorithm, the space complexity is O(1).

Conclusion

This article extensively discussed the problem of rotating a matrix by 180 degrees without using extra space.

We hope this blog has helped you enhance your knowledge regarding multi-dimensional array problems. After reading about the rotation of matrix, are you not feeling excited to read/explore more articles on this topic? Don't worry; Coding Ninjas has you covered. To learn, see time complexity, and Complexity Analysis.

Check out this problem - Matrix Median

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
Rotate a Matrix 90 Degrees (Without using Extra Space)
Next article
Rotate a Matrix Right by K Elements
Live masterclass