Rotate a matrix by 90 degrees

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]