### 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 arrayint[,] 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 16then we rotate the following diamond which is sort of askew

2 8 9 15and then the 2nd skewed diamond

3 5 12 14so that takes care of the outer edge so essentially we do that one shell at a time until

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

6 7 10 11so now let's figure out the indices of each layer, assume we always work with the outermost layer, we are doing

[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 on and so on until we are halfway through the edge

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. 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:

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

As with all performance issues, measure, measure, measure!

interface IReadableMatrix { int GetValue(int x, int y); }If your Matrix already implements this interface, then it can be rotated via a decorator class like this:

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); } }Rotating +90/-90/180 degrees, flipping horizontally/vertically and scaling can all be achieved in this fashion as well.

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

#include

ReplyDeletevoid main()

{

int mat1[3][3],mat2[3][3],i ,j;

static int k=0;

printf("Enter the values for the matrix \n");

for(i=0;i<3;i++)

{

printf("\n");

for(j=0;j<3;j++)

{

scanf("%d",&mat1[i][j]);

}

}

printf("Printing the given matrix");

for(i=0;i<3;i++)

{

printf("\n");

for(j=0;j<3;j++)

{

printf("%d ",mat1[i][j]);

}

}

printf("Rotating the given matrix by 90 degrees");

for(i=2;i>=0;--i)

{

// printf("\n");

for(j=0;j<3;j++)

{

mat2[j][k]=mat1[i][j];

}

k=k+1;

}

printf("Printing the rotated matrix ");

printf("\n"); printf("\n"); printf("\n");

for(i=0;i<3;i++)

{

printf("\n");

for(j=0;j<3;j++)

{

mat1[i][j]=mat2[i][j];

printf("%d ",mat1[i][j]);

}

}

}

Thanks for sharing. What I love the most about this post is the visual aspect of it, you really spent some time illustrating what rotating matrices meant in a very understandable set of images.

ReplyDeletekeep on the good work

Thanks andreea. :)

DeleteGood program thanks..

ReplyDeleteHere is my simple code for rotation of matrix by 90 degrees

Rotate array by 90 degrees