Sunday 26 January 2014

Program to rotate a matrix by 90 degree clockwise.

Question :

You have to rotate the matrix by 90 degrees.
For example if you have

[1][2][3][4]
[5][6][7][8]
[9][0][1][2]
[3][4][5][6]
 
output must be
 
[3][9][5][1]
[4][0][6][2]
[5][1][7][3]
[6][2][8][4] 


Solution : 

 package Matrices;

import java.util.Arrays;

/**
 * Created by Aniket on 1/26/14.
 */
public class NinetyDegRotator {

    public static int [][] rotate(int [][] matrix){
        int rows = matrix.length;
        int cols = matrix[0].length;
        int [][] rotatedMatrix = new int[rows][cols];
        for(int i =0; i<rows;i++){
            for(int j=0;j<cols;j++){
                rotatedMatrix[i][j] = matrix[cols-j-1][i];
            }
        }
        return rotatedMatrix;
    }

    public static void twoDArrayPrinter(int [][] matrix){

        for(int []array : matrix){
            System.out.println(Arrays.toString(array));
        }

    }

    public static void main(String args[]){

        int [][] matrix = new int[][]{
                {1,2,3,4},
                {5,6,7,8},
                {9,0,1,2},
                {3,4,5,6}
        };

        System.out.println("Original Array : ");
        NinetyDegRotator.twoDArrayPrinter(matrix);
        int [][] rotatedMatrix = ninetyDegRotator.rotate(matrix);
        System.out.println("Rotated Array : ");
        NinetyDegRotator.twoDArrayPrinter(rotatedMatrix);
    }

}

Output :

Original Array :
[1, 2, 3, 4]
[5, 6, 7, 8]
[9, 0, 1, 2]
[3, 4, 5, 6]
Rotated Array :
[3, 9, 5, 1]
[4, 0, 6, 2]
[5, 1, 7, 3]
[6, 2, 8, 4]

Note : Above algorithm takes O(N^2) time complexity.

 To make the transformation in place it has to be a square matrix(n*n)

Code :

package Matrices;

/**
 * Created by Aniket on 1/26/14.
 */
public class TransposeCreator {
    public static void inPlaceTranspose(int [][] matrix){

        int rows = matrix.length;
        int cols = matrix[0].length;

        for(int i=0;i<rows;i++){
            for(int j=i+1;j<cols;j++){
                matrix[i][j] = matrix[i][j] + matrix[j][i];
                matrix[j][i] = matrix[i][j] - matrix[j][i];
                matrix[i][j] = matrix[i][j] - matrix[j][i];
            }
        }
    }

    public static int[][] transpose(int[][] matrix){

        int rows = matrix.length;
        int cols = matrix[0].length;

        int[][] transposedMatrix = new int[cols][rows];

        for(int i=0;i<cols;i++){
            for(int j=0;j<rows;j++){
                transposedMatrix[i][j] = matrix[j][i];
            }
        }

        return transposedMatrix;

    }

    public static void inPlaceRowsSwapper(int [][] matrix){
        int rows = matrix.length;
        int cols = matrix[0].length;

        for(int i=0;i<rows;i++){
            for(int j=0;j<cols/2;j++){
                matrix[i][j] = matrix[i][j] + matrix[i][cols-j-1];
                matrix[i][cols-j-1] = matrix[i][j] - matrix[i][cols-j-1];
                matrix[i][j] = matrix[i][j] - matrix[i][cols-j-1];
            }
        }

    }


    public static void main(String args[]){

        int [][] matrix = new int[][]{
                {1,2,3,4},
                {5,6,7,8},
                {9,0,1,2},
                {3,4,5,6}
        };

        System.out.println("Original Array : ");
        NinetyDegRotator.twoDArrayPrinter(matrix);
        System.out.println("Transposed Matrix");
        NinetyDegRotator.twoDArrayPrinter(TransposeCreator.transpose(matrix));
        TransposeCreator.inPlaceTranspose(matrix);
        System.out.println("InPlace Transposed matrix");
        NinetyDegRotator.twoDArrayPrinter(matrix);
        System.out.println("90deg rotation matrix");
        TransposeCreator.inPlaceRowsSwapper(matrix);
        NinetyDegRotator.twoDArrayPrinter(matrix);

    }
}




Output :

Original Array :
[1, 2, 3, 4]
[5, 6, 7, 8]
[9, 0, 1, 2]
[3, 4, 5, 6]
Transposed Matrix
[1, 5, 9, 3]
[2, 6, 0, 4]
[3, 7, 1, 5]
[4, 8, 2, 6]
InPlace Transposed matrix
[1, 5, 9, 3]
[2, 6, 0, 4]
[3, 7, 1, 5]
[4, 8, 2, 6]
90deg rotation matrix
[3, 9, 5, 1]
[4, 0, 6, 2]
[5, 1, 7, 3]
[6, 2, 8, 4]
t> UA-39527780-1 back to top