Rotate a matrix by 90 degree without using any extra space | Set 2

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

Examples: 

Input:
 1  2  3
 4  5  6
 7  8  9
Output:
 3  6  9 
 2  5  8 
 1  4  7 
Rotated the input matrix by
90 degrees in anti-clockwise direction.
Input:
 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
Rotated the input matrix by
90 degrees in anti-clockwise direction.

An approach that requires extra space is already discussed in a different article: 
Inplace rotate square matrix by 90 degrees | Set 1

This post discusses the same problem with a different approach which is space-optimized.
Approach: The idea is to find the transpose of the matrix and then reverse the columns of the transposed matrix. 
Here is an example to show how this works. 

Algorithm:  

1. To solve the given problem there are two tasks. 1st is finding the transpose and the second is reversing the columns without using extra space
2. A transpose of a matrix is when the matrix is flipped over its diagonal, i.e the row index of an element becomes the column index and vice versa. So to find the transpose interchange of the elements at position (i, j) with (j, i). Run two loops, the outer loop from 0 to row count and the inner loop from 0 to the index of the outer loop.
3. To reverse the column of the transposed matrix, run two nested loops, the outer loop from 0 to column count and the inner loop from 0 to row count/2, interchange elements at (i, j) with (i, row[count-1-j]), where i and j are indices of inner and outer loop respectively.

Implementation:

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

Complexity Analysis: 

• Time Complexity: O(R*C). 
  The matrix is traversed twice, so the complexity is O(R*C).
• Auxiliary Space: O(1). 
  The space complexity is constant as no extra space is required.

Another Approach using a single traversal of the matrix :

The idea is to traverse along the boundaries of the matrix and shift the positions of the elements in 90⁰ anticlockwise directions in each boundary. There are such (n/2-1) boundaries in the matrix.

Algorithm: 

1. Iterate over all the boundaries in the matrix. There are total (n/2-1) boundaries
2. For each boundary take the 4 corner elements and swap them such that the 4 corner elements get rotated in anticlockwise directions. Then take the next 4 elements along the edges(left, right, top, bottom) and swap them in an anticlockwise direction. Continue as long as all the elements in that particular boundary get rotated in 90⁰ anticlockwise directions.
3. Then move on to the next inner boundary and continue the process as long the whole matrix is rotated in 90⁰ anticlockwise direction.

Original array

total n/2-1 boundaries

for outermost boundary

for next inner boundary

 Implementation:

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

Complexity Analysis: 

Time Complexity: O(R*C). The matrix is traversed only once, so the time complexity is O(R*C).
Auxiliary Space: O(1). The space complexity is O(1) as no extra space is required.

Implementation: Let’s see a method of Python numpy that can be used to arrive at the particular solution. 

Output:  

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

Note: The above steps/programs do left (or anticlockwise) rotation. Let’s see how to do the right rotation or clockwise rotation. The approach would be similar. Find the transpose of the matrix and then reverse the rows of the transposed matrix. 
This is how it is done. 

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

Rotating Along the Boundaries

We can start at the first 4 corners of the given matrix and then keep incrementing the row and column indices to moves around.

At any given moment we will have four corners lu (left-up),ld(left-down),ru(right-up),rd(right-down).

To left rotate we will first swap the ru and ld,  then lu and ld and lastly ru and rd.

Implementation:

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

Time Complexity: O(n²)
Auxiliary Space: O(1), since no extra space has been taken.