Rotating a 2D array of integers (matrix) by a given angle (+90, -90, +180, -180)

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''

1 4 7              7 4 1
2 5 8      --     8 5 2
3 6 9              9 6 3

M'' is rotated form of M by +90 degree.

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