Monday, December 8, 2014

Square matrix rotation [in-place] [Coding Question][Java]

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

Source:

import java.util.Arrays;

public class Code { 
    
    //Method #1
    public static void rotate1(int[][] array){
        int TL = 0, TR = array.length-1;
        
        while(TL<TR){
            int TR1 = TR; 
            
            for(int i=TL;i<TR;++i){
                int savedTL = array[TL][i];
                array[TL][i] = array[TR1][TL];
                array[TR1][TL] = array[TR][TR1];
                array[TR][TR1--] = array[i][TR];
                array[i][TR] = savedTL; 
            }
            TL++;   TR--;
        }
    }
     
    //Method #2 - Costlier
    public static void rotate2(int[][] array){
        int TL = 0, TR = array.length-1;
        
        while(TL<TR){
            int TR1 = TR; 
            
            for(int i=TL;i<TR;++i){ 
                exchange(TL, i, i, TR, array);
                exchange(TL, i, TR, TR1, array);
                exchange(TL, i, TR1--, TL, array);
            }
            TL++;   TR--;
        }
    }
    
    public static void exchange(int i1, int j1, int i2, int j2, int[][] array){
        int temp = array[i1][j1];
        array[i1][j1] = array[i2][j2];
        array[i2][j2] = temp;
    }
    
    public static void main(String[] args){
        int[][] array = { {5, 3, 7, 6},
                          {7, 1, 9, 5},
                          {4, 2, 3, 4},
                          {2, 0, 7, 8},}; 
        rotate1(array);
        System.out.println(Arrays.deepToString(array));
        
        array = new int[][]{{1, 2, 3},
                            {4, 5, 6},
                            {7, 8, 9}};
        rotate1(array);
        System.out.println(Arrays.deepToString(array));  
        
        array = new int[][]{{1, 2},
                            {3, 4}};
        rotate1(array);
        System.out.println(Arrays.deepToString(array));
        
        array = new int[][]{{1}}; 
        rotate1(array);
        System.out.println(Arrays.deepToString(array));
    }
}

Output:

[[2, 4, 7, 5], [0, 2, 1, 3], [7, 3, 9, 7], [8, 4, 5, 6]]
[[7, 4, 1], [8, 5, 2], [9, 6, 3]]
[[3, 1], [4, 2]]
[[1]]

No comments:

Post a Comment