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]