Inplace rotate square matrix by 90 degrees | Set 1

Given a square matrix, turn it by 90 degrees in an anti-clockwise direction without using any extra space

Examples: 

Input:
Matrix:    1  2  3
               4  5  6
               7  8  9

Output:  3  6  9 
               2  5  8 
               1  4  7 

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

Note: An approach that requires extra space is already discussed here.

Example no1 – Inplace rotate square matrix by 90 degrees by forming cycles:

To solve the problem follow the below idea:

To solve the question without any extra space, rotate the array in form of squares, dividing the matrix into squares or cycles. For example, 
A 4 X 4 matrix will have 2 cycles. The first cycle is formed by its 1st row, last column, last row, and 1st column. The second cycle is formed by the 2nd row, second-last column, second-last row, and 2nd column. The idea is for each square cycle, to swap the elements involved with the corresponding cell in the matrix in an anti-clockwise direction i.e. from top to left, left to bottom, bottom to right, and from right to top one at a time using nothing but a temporary variable to achieve this

Dry run of the above approach:

First Cycle:

 1  2  3 4 
 5  6  7 8 
 9 10 11 12 
13 14 15 16 

Moving first group of four elements (elements 
of 1st row, last row, 1st column and last column) of first cycle 
in counter clockwise. 

 4  2  3 16
 5  6  7 8 
 9 10 11 12 
 1 14  15 13 

 Moving next group of four elements of 
first cycle in counter clockwise 

 4  8  3 16 
 5  6  7  15  
 2  10 11 12 
 1  14  9 13 

Moving final group of four elements of 
first cycle in counter clockwise 

 4  8 12 16 
 3  6  7 15 
 2 10 11 14 
 1  5  9 13 

Second Cycle:

 4  8 12 16 
 3  6 7  15 
 2  10 11 14 
 1  5  9 13 

Fixing second cycle

 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.

Below is the implementation of the above approach:

4 8 12 16 
3 7 11 15 
2 6 10 14 
1 5 9 13 

Time Complexity: O(N²), 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

Example no 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

Below is the implementation of the above approach:

4 8 12 16 
3 7 11 15 
2 6 10 14 
1 5 9 13 

Time Complexity: O(N²) + O(N²)  where N is the size of the array.
Auxiliary Space: O(1). As a constant space is needed

Example no 3 – Implementation by using Vectors in c++

Input - Matrix

1 2 3 
4 5 6 
7 8 9 

Algorithmic steps for implementation –

the algorithmic steps to in-place rotate a square matrix by 90 degrees:

1. Transpose the matrix: For each element matrix[i][j] where i < j, swap it with the element matrix[j][i].
2. Reverse each row of the matrix: For each row i of the matrix, reverse the order of the elements by swapping matrix[i][j] with matrix[i][n – j – 1] where n is the number of columns in the matrix.
3. The matrix is now rotated by 90 degrees in place.

Note: The first step transforms the matrix into its transposed form, and the second step reverses the elements in each row, resulting in a rotation of the matrix by 90 degrees.

 Program –

3 6 9 
2 5 8 
1 4 7 

Explanation –

• In this implementation, the rotateMatrix function takes a 2D vector matrix as input and rotates the matrix by 90 degrees in the anticlockwise direction in place.
  The first step is to transpose the matrix, which is done by swapping the elements matrix[i][j] and matrix[j][i] for i < j.
  The second step is to reverse each column of the matrix, which is done by swapping the elements matrix[j][i] and matrix[n – j – 1][i] where n is the number of rows in the matrix.
• The time complexity of this algorithm is O(n^2), where n is the number of rows (and columns) in the matrix. This is because the algorithm performs a constant amount of work for each element in the matrix.
• The Auxiliary Space needed for this algorithm is O(1), since no extra space is used.

Exercise: Turn the 2D matrix by 90 degrees in a clockwise direction without using extra space.
Rotate a matrix by 90 degrees without using any extra space | Set 2

This article is contributed by Aditya Goel. If you like neveropen and would like to contribute, you can also write an article and mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.