Monthly Archives: May 2014

Spiral matrix

In this post I would be discussing the implementation of a program to fill a square double dimension array in a circular fashion, also known as spiral matrix due to it’s appearance. This problem on cyclic filling of an array was asked in the ISC Computer Science Practical Examination 1998.

The problem can be easily solved, if we break it into four parts, one for each direction. We will have one loop for filling the array from left to right (lr), one loop for spiral matrixfilling the array from top to bottom (tb), one for filling the array from right to left (rl) and for filling the array from bottom to top (bt). The above step would be repeated till all number from 1 to n2 are filled up for a square array of n x n. We would be requiring four variables to keep track of limits in all the four direction (l1, l2, l3, l4).

The Java program for filling the array in a circular fashion (spiral matrix/cyclic filling) is as follows:

class Cyclic{
    public static int[][] fillCyclic( int n ){
        int a[][] = new int[n][n];
        int square = n*n;
        int l1 = 0,
            l2 = 0,
            l3 = n-1,
            l4 = n-1,
            c=1;
        while(true){
            for( int lr = l1; lr <= l3; lr++ ){ // left to right
                a[l2][lr] = c++;
            }
            l2++;
            for( int tb = l2; tb <= l4 ; tb++ ){ // top to bottom
                 a[tb][l3] = c++;
            }
            l3--; 
            for( int rl = l3; rl >=l1 ; rl-- ){ // right to left
                a[l4][rl] = c++;
            }
            l4--;
            for( int bt = l4; bt >=l2 ; bt-- ){ // bottom to top
                a[bt][l1] = c++;
            }
            l1++;
            if(c>square) break;
        }
        return a;
    }
    public static void displayArray( int a[][] ){
        for( int i = 0; i < a.length ; i++ ){
            for( int j = 0; j < a[i].length; j++ ){
                System.out.print( a[ i ][ j ] + "\t" );
            }
            System.out.println();
        }
    }
    public static void main( String args[] ){
        int a[][] = fillCyclic( 6);
        displayArray(a);
        System.out.println();
        a = fillCyclic( 7 );
        displayArray(a);
    }
}

The output  of the above program for cyclically filling an array for 6 x 6 and 7 x 7 is as follows:

1	2	3	4	5	6	
20	21	22	23	24	7	
19	32	33	34	25	8	
18	31	36	35	26	9	
17	30	29	28	27	10	
16	15	14	13	12	11	

1	2	3	4	5	6	7	
24	25	26	27	28	29	8	
23	40	41	42	43	30	9	
22	39	48	49	44	31	10	
21	38	47	46	45	32	11	
20	37	36	35	34	33	12	
19	18	17	16	15	14	13	

The above logic can be modified to cater for rectangular two dimensional array by proper initialisation of the initial values of limits i.e. l1, l2, l3 & l4 and checking for completion after filling in each direction, as follows:

class CyclicRectangle{
    public static int[][] fillCyclic(int m,  int n){
        int a[][] = new int[m][n];
        int square = m*n;
        int l1 = 0,
        l2 = 0,
        l3 = n-1,
        l4 = m-1,
        c=1;
        while(true){
            for( int lr = l1; lr <= l3; lr++ ){
                a[l2][lr] = c++;
            }
            l2++;
            if(c>square) break;
            for( int tb = l2; tb <= l4 ; tb++ ){ 
                a[tb][l3] = c++; 
            } 
            l3--; 
            if(c>square) break;
            for( int rl = l3; rl >=l1 ; rl-- ){
                a[l4][rl] = c++;
            }
            l4--;
            if(c>square) break;
            for( int bt = l4; bt >=l2 ; bt-- ){
                a[bt][l1] = c++;
            }
            l1++;
            if(c>square) break;
        }
            return a;
    }
    public static void displayArray( int a[][] ){
        for( int i = 0; i < a.length ; i++ ){
            for( int j = 0; j < a[i].length; j++ ){
                System.out.print( a[ i ][ j ] + "\t" );
            }
            System.out.println();
        }
    }

    public static void main( String args[] ){
        int a[][] = fillCyclic(3,2);
        displayArray(a);
    }
}

 

As usual, the main function has purposely been kept to minimum and its expected that students will write appropriate input/output statements as per the requirement.