Set-1
In this given set-1 the problem statement is like Given a square matrix, turn it by 90 degrees in an anti-clockwise direction without using any extra space.
Input:
Matrix: 1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
Output: 4 8 12 16
3 7 11 15
2 6 10 14
1 5 9 13
Follow the given steps to solve the problem:
- There are N/2 squares or cycles in a matrix of side N. Process a square one at a time. Run a loop to traverse the matrix a cycle at a time, i.e loop from 0 to N/2 – 1, loop counter is i
- Consider elements in group of 4 in current square, rotate the 4 elements at a time. So the number of such groups in a cycle is N – 2*i.
- So run a loop in each cycle from x to N – x – 1, loop counter is y
- The elements in the current group is (x, y), (y, N-1-x), (N-1-x, N-1-y), (N-1-y, x), now rotate the these 4 elements, i.e (x, y) <- (y, N-1-x), (y, N-1-x)<- (N-1-x, N-1-y), (N-1-x, N-1-y)<- (N-1-y, x), (N-1-y, x)<- (x, y)
- Print the matrix.
Code Implementation
// cskecode C++ program to rotate a matrix
// by 90 degrees
#include <bits/stdc++.h>
#define N 4
using namespace std;
// An Inplace function to
// rotate a N x N matrix
// by 90 degrees in
// anti-clockwise direction
void rotateMatrix(int mat[][N])
{
// Consider all squares one by one
for (int x = 0; x < N / 2; x++) {
// Consider elements in group
// of 4 in current square
for (int y = x; y < N - x - 1; y++) {
// Store current cell in
// temp variable
int temp = mat[x][y];
// Move values from right to top
mat[x][y] = mat[y][N - 1 - x];
// Move values from bottom to right
mat[y][N - 1 - x] = mat[N - 1 - x][N - 1 - y];
// Move values from left to bottom
mat[N - 1 - x][N - 1 - y] = mat[N - 1 - y][x];
// Assign temp to left
mat[N - 1 - y][x] = temp;
}
}
}
// Function to print the matrix
void displayMatrix(int mat[N][N])
{
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cout << mat[i][j] << " ";
}
cout << endl;
}
cout << endl;
}
/* Driver code */
int main()
{
// Test Case 1
int mat[N][N] = { { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 },
{ 13, 14, 15, 16 } };
// Function call
rotateMatrix(mat);
// Print rotated matrix
displayMatrix(mat);
return 0;
}
Time Complexity: O(N2), where n is the side of the array. A single traversal of the matrix is needed.
Auxiliary Space: O(1). As a constant space is needed
Set-2
Inplace rotate square matrix by 90 degrees by transposing and reversing the matrix:
Follow the given steps to solve the problem:
- Reverse every individual row of the matrix
- Perform Transpose of the matrix
Code implementation
// Cskecode C++ program to rotate a matrix
// by 90 degrees
#include <bits/stdc++.h>
using namespace std;
#define N 4
// An Inplace function to
// rotate a N x N matrix
// by 90 degrees in
// anti-clockwise direction
void rotateMatrix(int mat[][N])
{ // REVERSE every row
for (int i = 0; i < N; i++)
reverse(mat[i], mat[i] + N);
// Performing Transpose
for (int i = 0; i < N; i++) {
for (int j = i; j < N; j++)
swap(mat[i][j], mat[j][i]);
}
}
// Function to print the matrix
void displayMatrix(int mat[N][N])
{
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cout << mat[i][j] << " ";
}
cout << endl;
}
cout << endl;
}
/* Driver code */
int main()
{
int mat[N][N] = { { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 },
{ 13, 14, 15, 16 } };
// Function call
rotateMatrix(mat);
// Print rotated matrix
displayMatrix(mat);
return 0;
}
Time Complexity: O(N2) + O(N2) where N is the size of the array.
Auxiliary Space: O(1). As a constant space is needed
