Rotate n * n matrix by 90 degrees

Problem

Rotate the n*n matrix by 90 degrees.

**Another way to ask the same problem **

Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place?

Example

       Example 1                          Example 2  
INPUT    >>     OUTPUT      |         INPUT    >>  OUTPUT    
                            |  
4                           |             4                                           
                            |  
1 2 3 4        1 1 1 1      |     11 12 13 14      41 31 21 11  
                            |  
1 2 3 4        2 2 2 2      |     21 22 23 24      42 32 22 12  
                            |  
1 2 3 4        3 3 3 3      |     31 32 33 34      43 33 23 13  
                            |  
1 2 3 4        4 4 4 4      |     41 42 43 44      44 34 24 14

Solution

Consider the array

int\[,\] array = new int\[4,4\] {  
    { 1,2,3,4 },  
    { 5,6,7,8 },  
    { 9,0,1,2 },  
    { 3,4,5,6 }  
};

Method 1 - Using 2D array of same size
Here we are

//runner method call  
int\[,\] rotated = RotateMatrix(array, 4);  
  
static int\[,\] RotateMatrix(int\[,\] matrix, int n) {  
    int\[,\] ret = new int\[n, n\];  
  
    for (int i = 0; i < n; ++i) {  
        for (int j = 0; j < n; ++j) {  
            ret\[i, j\] = matrix\[n - j - 1, i\];  
        }  
    }  
  
    return ret;  
}

Lets understand this by example.
Consider the array :

Now, when i=0 and j=0, we insert matrix[n-1,0] to ret[0,0]

Similarily we continue for i=0, and iterating over j.

Now, i=1, and iterating over j :

Complexity
Time complexity - O(n^2)
Space complexity - O(n^2)

But as we are using lots of space, can we do better?

Method 2 - Without using any extra spaces but O(n^2)
This example is taken from here. Here is the basic algo:

Iterate over the 2D array with i and j iterators to the size of N/2
Now take the corner elements based on i and j, and swap them accordingly

Java Code

public static void rotate(int\[\]\[\] matrix) {  
    int N = matrix.length;  
    for(int i = 0; i < N/2; ++i) {  
        for(int j = 0; j < (N+1)/2; ++j) {  
            int temp = matrix\[i\]\[j\];  // save the top element;  
            matrix\[i\]\[j\] = matrix\[N-1-j\]\[i\];  // right -> top;  
            matrix\[N-1-j\]\[i\] = matrix\[N-1-i\]\[N-1-j\]; // bottom -> right;  
            matrix\[N-1-i\]\[N-1-j\] = matrix\[j\]\[N-1-i\];// left -> bottom;  
            matrix\[j\]\[N-1-i\] = temp;                // top -> left;  
        }  
    }  
}

Time complexity - O(n^2)
Space complexity - O(1)

Example
Consider the following matrix with N = 4

**i=0,j=0 **

Now we see that 1,4,13 and 16 are at the right place. Lets iterate further
i=0,j=1

Similarly we will go on.
Finally we will get following :

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

So, to sum up we were doing this:

1           4  
  
  
13          16  

```then we rotate the following diamond which is sort of askew

2  
        8

9
15

5
12
14

finally the middle square (or if it's odd just the final element which does not move)

6 7
10 11

[0,0] -> [0,n-1], [0,n-1] -> [n-1,n-1], [n-1,n-1] -> [n-1,0], and [n-1,0] -> [0,0]
[0,1] -> [1,n-1], [1,n-2] -> [n-1,n-2], [n-1,n-2] -> [n-2,0], and [n-2,0] -> [0,1]
[0,2] -> [2,n-2], [2,n-2] -> [n-1,n-3], [n-1,n-3] -> [n-3,0], and [n-3,0] -> [0,2]

so in general the pattern is

[0,i] -> [i,n-i], [i,n-i] -> [n-1,n-(i+1)], [n-1,n-(i+1)] -> [n-(i+1),0], and [n-(i+1),0] to [0,i]

Can we do better. It may not look obvious, but yes we can. Here is the next solution:  
  
**Method 3 - Adding decorator on the top of matrix**  
This method has been suggested by Drew [here](http://stackoverflow.com/a/193942/3222727). Just keeping it here:  

Whilst rotating the data in place might be necessary (perhaps to update the physically stored representation), it becomes simpler and possibly more performant to add a layer of indirection onto the array access, perhaps an interface:

interface IReadableMatrix
{
int GetValue(int x, int y);
}

class RotatedMatrix : IReadableMatrix
{
private readonly IReadableMatrix _baseMatrix;

public RotatedMatrix(IReadableMatrix baseMatrix)  
{  
    \_baseMatrix = baseMatrix;  
}  

int GetValue(int x, int y)  
{  
    // transpose x and y dimensions  
    return \_baseMatrix(y, x);  
}

}

Performance would need to be measured in your specific scenario. However the O(n^2) operation has now been replaced with an O(1) call. It's a virtual method call which _is_ slower than direct array access, so it depends upon how frequently the rotated array is used after rotation. If it's used once, then this approach would definitely win. If it's rotated then used in a long-running system for days, then in-place rotation might perform better. It also depends whether you can accept the up-front cost.  
As with all performance issues, measure, measure, measure!

  
  
**Reference**  

*   [http://stackoverflow.com/questions/42519/how-do-you-rotate-a-two-dimensional-array](http://stackoverflow.com/questions/42519/how-do-you-rotate-a-two-dimensional-array)

Problem

Solution

See also