Thursday, October 24, 2013

Coding Question: rotate a NxN matrix by 90 degrees in-place

Question:
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?

Solution:


#include <iostream>
using namespace std;

void rotate90(int **array, int N){
    for(int i=0;i<N/2;++i){
        for(int j=i;j<N-1-i;++j){
	    int t1=array[j][N-1-i];
	    array[j][N-1-i] = array[i][j];

            int t2=array[N-1-i][N-1-j];
            array[N-1-i][N-1-j] = t1;

            t1 = array[N-1-j][i];
            array[N-1-j][i] = t2;

            array[i][j] = t1;
       }
    }
}

int main() {
    int **matrix;
    matrix = new int*[5];
    for(int i=0;i<5;++i)
        matrix[i] = new int[5];

    int count=0;
    for(int i=0;i<5;++i)
        for(int j=0;j<5;++j){
        matrix[i][j] = count++;
		}

    for(int i=0;i<5;++i){
       for(int j=0;j<5;++j){
           cout<<matrix[i][j]<<" ";
       }
       cout<<endl;
    }
    cout<<"----------------"<<endl;
    rotate90(matrix,5);
    for(int i=0;i<5;++i){
        for(int j=0;j<5;++j){
            cout<<matrix[i][j]<<" ";
        }
        cout<<endl;
    }
    //release memory
    for(int i=0;i<5;++i){
       delete[] matrix[i];
    }
    delete[] matrix;
    cout << "" << endl; // prints 
    return 0;
}

No comments:

Post a Comment