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]

Advertisements

8 thoughts on “Rotate a matrix by 90 degrees

  1. Congrats for this new baby XD ! cheers! dude

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

  3. Great post Alberto! I like this post!

  4. 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?

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

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

  7. for(i=0;i=0;j–)
    {
    cout<<a[j][I]<<"\t";
    }
    cout<<endl;
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s