In-place rotate matrix by 90 degrees in clock-wise direction

Given a square matrix, rotate matrix by 90 degrees in clock-wise direction. The transformation should be done in-place and in quadratic time.


 
For example,


Input:

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

Output:

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

 


 
The idea is to in-place convert the matrix into its transpose first. Then if we swap first column with the last column, second column with the second last column, and so on.. we will get our desired matrix.

C++

Download   Run Code


Output:

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

 

If we were asked to rotate the matrix in anti-clockwise manner, we can easily do that too using the same logic. The only difference is that instead of swapping columns, we swap rows.

C++

Download   Run Code


Output:

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

 
Time complexity of above solution is O(N2) and auxiliary space used by the program is O(1).

 
Exercise: In-place rotate the matrix by 180 degrees

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
Rajendra
Guest
Rajendra

Hey! Great blog.

To rotate by 180 degree clockwise, we can rotate the matrix by 90 degree clockwise twice. Similarly for 180 degree anti-clockwise.

180 degree clockwise: but we can do much better by reversing each row in first pass and then reversing each column in the second.

I had written a detailed article few years back on this problem here. https://goo.gl/L3IlBc

wpDiscuz