Problem description: Given an N X N integer matrix, rotate it bye 90 degrees in place.

eg.

**[1, 2, 3, 4] [9, 6, 9, 1]**

**[9, 8, 5, 6] –> [2, 5, 8, 2]**

**[6, 5, 3, 7] [6, 3, 5, 3]**

**[9, 2, 6, 8] [8, 7, 6, 4]**

Solution:

The key is to solve this problem in “layers” from outer ones to inner ones as follows:

In our example we have two layers:

OUTER LAYER INNER LAYER

1 2 3 4

9 6 8 5

6 7 5 3

9 2 6 8

The idea is to do a “four-way” swap variable, we need to move the values from top -> right, right -> bottom, bottom -> left and left -> top, can we do it by using only one extra variable? Yes, we can.

At each layer we are gonna loop through the elements and swap them as follows:

1.- Save the ith element in the top array in a temporary variable (in our example the top array is [1 2 3 4] ).

2.- Move the ith element from left to top.

3.- Move the ith element from bottom to left.

4.- Move the ith element from right to bottom.

5.- Save the value of our temporary variable in the ith position in the right array.

Here is the code in Python:

#!/usr/bin/python -tt import sys #create a N X N matrix def getMatrix(n): matrix = [] for i in range(n): inside = [] for j in range(n): inside.append(j + i + 2) matrix.append(inside) return matrix #print the matrix def printMatrix(m): for row in m: print row print #rotate the matrix by 90 degrees (clockwise) in place def rotate90Degrees(m): layers = len(m) / 2 length = len(m) - 1 for layer in range(layers): #for each layer for i in range(layer, length - layer): # loop through the elements we need to change at each layer temp = m[layer][i] #save the top element, it takes just one variable as extra memory #Left -> Top m[layer][i] = m[length - i][layer] #Bottom -> left m[length - i][layer] = m[length - layer][length - i] #Right -> bottom m[length - layer][length - i] = m[i][length - layer] #Top -> Right m[i][length - layer] = temp #main function def main(): #it takes values from stdin for line in sys.stdin: n = int(line) print "N = "+ str(n) matrix = getMatrix(n) print "Original matrix:\n" printMatrix(matrix) rotate90Degrees(matrix) print "Rotate matrix by 90 degrees:\n" printMatrix(matrix) if __name__ == '__main__': main()

Some input/output samples:

N = 4

Original matrix:

[2, 3, 4, 5]

[3, 4, 5, 6]

[4, 5, 6, 7]

[5, 6, 7, 8]

Rotate matrix by 90 degrees:

[5, 4, 3, 2]

[6, 5, 4, 3]

[7, 6, 5, 4]

[8, 7, 6, 5]

************************************

N = 2

Original matrix:

[2, 3]

[3, 4]

Rotate matrix by 90 degrees:

[3, 2]

[4, 3]

*************************************

N = 5

Original matrix:

[2, 3, 4, 5, 6]

[3, 4, 5, 6, 7]

[4, 5, 6, 7, 8]

[5, 6, 7, 8, 9]

[6, 7, 8, 9, 10]

Rotate matrix by 90 degrees:

[6, 5, 4, 3, 2]

[7, 6, 5, 4, 3]

[8, 7, 6, 5, 4]

[9, 8, 7, 6, 5]

[10, 9, 8, 7, 6]

Congrats for this new baby XD ! cheers! dude

I wanna say thanks for posting this awesome information. Keep up the great job. I’ll subscribe to your weblog also. thnx!

Great post Alberto! I like this post!

Hi there. I’m a junior developer, and have been looking for resources on algorithms. Your blog is a great resource, and thank you. I do not understand how it is possible to have more than one value in the append() function. Can you explain this?

For Matrix, it append a list, one value;

For inside, it’s a list, it append a value, so it’s still one value.

Liked your solution because of simplicity. Here is my solution with O(1) space –

here

If I transpose the matrix and then reverse each row ….

I have written the code here

private static void rotateMatrix(int mat[][],int dimension){

//int j=0;

int temp=0;

int i=0,j=0;

for( i=0;i<dimension;i++){

j=i;

for(int count=0;count<dimension-i;count++){

if((j+1)<=(dimension-1)){

temp=mat[i][j+1];

mat[i][j+1]=mat[j+1][i];

mat[j+1][i]=temp;

}

j++;

}

}

int lower=0;

int upper=dimension-1;

for(i=0;i<dimension;i++){

lower=0;

upper=dimension-1;

while(lower<=upper){

temp=mat[i][lower];

mat[i][lower]=mat[i][upper];

mat[i][upper]=temp;

lower++;

upper–;

}

}

}

Please correct me if my approach is wrong

for(i=0;i=0;j–)

{

cout<<a[j][I]<<"\t";

}

cout<<endl;

}