We are given an NxN matrix and we have to rotate it by 90 degrees in a clockwise direction without using any extra space.
Input: 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 Output: 22 18 14 10 23 19 15 11 24 20 16 12 25 21 17 13
We will tackle this problem by first rotating the outmost matrix and working all the way inwards.
Let a 3X3 matrix:
10 11 12 13
14 15 16 17
18 19 20 21
22 23 24 25
step 1: (rotating outer matrix)
22 11 12 10
14 15 16 17
18 19 20 21
25 23 24 13
step 2:
22 18 12 10
14 15 16 11
24 19 20 21
25 23 17 13
step 3:
22 18 14 10
23 15 16 11
24 19 20 12
25 21 17 13
step 4: (rotating inner matrix)
22 18 14 10
23 19 15 11
24 20 16 12
25 21 17 13
Important thing is that we will run the outer loop (i) only lower bound of half the size of the row or column and the inner loop will start from the current value of the outer loop ( for(j = i; …….) ) and will run till the size of row/column – outer loop count ( for(j=i; j < (size -i -1); j++) )times.
Why? In step 4, we are rotating the inner matrix, so we want our inner loop to run only from index 1 up to index 2, not up to index 3(Here we are considering rows and columns starting from 0,0).
CPP code for rotating matrix in the clockwise direction by 90 degrees
#include <bits/stdc++.h> using namespace std; int matrix_rotation(vector<vector<int> > &matrix, int size){ int i,j; for(i=0;i<size/2;i++){ for(j=i;j<size-i-1;j++){ int tmp = matrix[i][j]; matrix[i][j] = matrix[size-j-1][i]; matrix[size-j-1][i] = matrix[size-i-1][size-j-1]; matrix[size-i-1][size-j-1] = matrix[j][size-i-1]; matrix[j][size-i-1] =tmp; } } return 0; } int main(){ int val =10,size = 4; vector<vector<int> >matrix; for(int i=0;i<size;i++){ vector<int> vi; for(int j=0;j<size;j++){ vi.push_back(val); val++; } matrix.push_back(vi); } for(int i=0;i<size;i++){ for(int j=0;j<size;j++) cout<<matrix[i][j]<<" "; cout<<endl; } matrix_rotation(matrix, size); cout<<"\nMatrix after rotating 90 degrees\n"<<endl; for(int i=0;i<size;i++){ for(int j=0;j<size;j++) cout<<matrix[i][j]<<" "; cout<<endl; } return 0; }
Output:
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 Matrix after rotating 90 degrees 22 18 14 10 23 19 15 11 24 20 16 12 25 21 17 13