So, I came across this problem on a forum and before looking up, I tried to solve it. After 15 minutes of trying, I figured out that the solution is pretty easy and elegant which was messy otherwise if you are going to do it in an insane way. So, here we go:
Problem definition: You are given a 2D square matrix, or 2D array of integers of size n (n rows and n columns), your output should be n by n 2D matrix rotated by a given angle, which could be +90, -90, +180, -180.
Example:
Input Output
1 2 3 7 4 1
4 5 6 Rotate by +90 8 5 2
7 8 9 9 6 3
If you go by solving it something like manually, swapping elements, its going to be messy, tedious, and error prone in that there will be much more edge cases, test cases to handle. So, after trying on paper, I figured out following elegant solution to solve this in an easy manner.
Rotate by +90 (clockwise once):
Input: n by n matrix M, where n >= 2
Algorithm:
Step 1: Transpose M
Step 2: Reverse each row
Dry run:
Step 1: Transpose
M M'
1 2 3 1 4 7
4 5 6 -- 2 5 8
7 8 9 3 6 9
Step 2: Reverse each row
M' M''
2 5 8 -- 8 5 2
3 6 9 9 6 3
Pseudocode: is here which is self explanatory and easily convertible to source code in a language of your choice.
Transpose
for i in [0, n)
for j in [0, n)
if ( i < j )
swap( M[i][j], M[j][i] )
Reverse a row (rowidx)
start = 0
end = cols - 1
while ( start < end ) {
swap( M[rowidx][start], M[rowidx][end] )
++start
--end
}
Rotate
Transpose
for i in [0, rows)
Reverse( i )
That was fair enough until only asked to rotate by +90 degree. If problem is further extended to be solved for any given angle, of course the rotation should make sense, for example, 47 degree is not a choice ;-). So, here are some elegant techniques (I'll be brief now for other angles, because for +90 degree I have elaborated the solution):
Rotation by -90 degree (anticlockwise once):
Step 1: Transpose
Step 2: Reverse each column
Rotation by +180 degree (clockwise twice): Two methods follows
First:
Rotate input matrix +90 degree twice, if routine for which is available to you
Second: (You'll be amazed!)
Step 1: Reverse each row
Step 2: Reverse each column
Rotation by -180 degree (anticlockwise twice): Three(!!!) methods follows
First:
Rotate input matrix -90 degree twice, if routine for which is available to you
Second: (You'll be amazed again!)
Step 1: Reverse each column
Step 2: Reverse each row
Third: (Aha!)
Because rotating a matrix +180 degree or -180 should produce same result. So you can rotate it by +180 degree using one of above methods.
Concluding note: Above techniques are elegant and very simple and straightforward to implement. Try them for some input of your choice and rotate it in all angles. These techniques are tested with a working C program.
Cheers!
Rajendra
