Print 2D Array Matrix Spiral Order

Question: Given a 2D array / matrix of integers. Write a program to print the elements in spiral order. Consider a matrix as show in the diagram to the right. The desired output of the program should be as: 1,2,3,4,8,12,16,20,19,18,17,13,9,5,6, 7,11,15,14,10.

matrix-spiral-print

Solution: There are several ways to solve this problem, but I am mentioning a method that is intuitive to understand and easy to implement. The idea is to consider the matrix similar to onion which can be peeled layer after layer. We can use the same approach to print the outer layer of the matrix and keep doing it recursively on a smaller matrix (with 1 less row and 1 less column).

Refer to the image below for a visual explanation. We start by printing the top-right layer of the matrix by calling the print_layer_top_right. It will print 1,2,3,4,8,12,16,20. The print_layer_top_right method then calls the print_layer_bottom_left method which will print 19,18,17,13,9,5. If you observe the size of the target matrix is reducing after each call. Each method basically calls the other method and passes the matrix indexes for the reduced matrix. Both methods take 4 index parameters which represent the target matrix. When the target matrix size is such that there is only one layer left the recursion terminates and by this time the code has printed all the numbers in the full matrix.

matrix-spiral-print-after-1st-iteration

Code (C language):
#include <stdio.h>
void print_layer_top_right(int a[][4], int x1, int y1, int x2, int y2);
void print_layer_bottom_left(int a[][4], int x1, int y1, int x2, int y2);

int main(void)
{
       int a[5][4] = {
                       {1,2,3,4},
                       {5,6,7,8},
                       {9,10,11,12},
                       {13,14,15,16},
                       {17,18,19,20}
                   };

       print_layer_top_right(a,0,0,3,4);
}

//
// prints the top and right shells of the matrix
//
void print_layer_top_right(int a[][4], int x1, int y1, int x2, int y2)
{
      int i = 0, j = 0;

      // print the row
      for(i = x1; i<=x2; i++)
      {
         printf("%d,", a[y1][i]);
      }
 
      //print the column         
      for(j = y1 + 1; j <= y2; j++)         
      {
         printf("%d,", a[j][x2]);
      }

      // see if  we have more cells left         
      if(x2-x1 > 0)
      {
          // 'recursively' call the function to print the bottom-left layer
          print_layer_bottom_left(a, x1, y1 + 1, x2-1, y2);
      }
}

//
// prints the bottom and left shells of the matrix
//
void print_layer_bottom_left(int a[][4], int x1, int y1, int x2, int y2)
{
       int i = 0, j = 0;

       //print the row of the matrix in reverse
       for(i = x2; i>=x1; i--)
       {
               printf("%d,", a[y2][i]);
       }

       // print the last column of the matrix in reverse
       for(j = y2 - 1; j >= y1; j--)
       {
               printf("%d,", a[j][x1]);
       }

       if(x2-x1 > 0)
       {
               // 'recursively' call the function to print the top-right layer
               print_layer_top_right(a, x1+1, y1, x2, y2-1);
       }
}

16 comments:

  1. plz tell me why u have used this 4

    (int a[][4], int x1, int y1, int x2, int y2);
    (int a[][4], int x1, int y1, int x2, int y2);

    ReplyDelete
  2. (int a[][4], int x1, int y1, int x2, int y2);
    (int a[][4], int x1, int y1, int x2, int y2);

    why u've used 4 in both of these functions

    ReplyDelete
  3. could u plz tell me the flow of the program

    and what is this?? "if(x2-x1 %gt; 0)"
    if(x2-x1 %gt; 0)
    {
    // 'recursively' call the function to print the bottom-left layer
    print_layer_bottom_left(a, x1, y1 + 1, x2-1, y2);
    }


    if(x2-x1 > 0)
    {
    // 'recursively' call the function to print the top-right layer
    print_layer_top_right(a, x1+1, y1, x2, y2-1);
    }

    ReplyDelete
  4. %gt; was typo while trying write the html encoding for > sign. It should be 'if(x2-x1 > 0)'. I have made the correction to the code above.
    Thanks for catching it.

    ReplyDelete
  5. You should change

    if(x2-x1 > 0)

    to

    if(x2-x1 > 0 && y2-y1 > 0)

    so you can support Matrix with more columns than rows.

    ReplyDelete
  6. This comment has been removed by the author.

    ReplyDelete
  7. This comment has been removed by the author.

    ReplyDelete
  8. can any one tell the solution to above problem with out using arrays

    ReplyDelete
  9. awesome concept bro and u have xplained it very wel
    thanks
    rahul...

    ReplyDelete
  10. CODE (JAVA)
    HOW ABOUT THIS LOGIC???


    import java.io.*;
    class spiralmatrix
    {
    static int a[][];
    public static void main(String arg[])throws IOException
    {
    BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
    System.out.println("enter size of matrix");
    int n=Integer.parseInt(br.readLine());
    a=new int[n][n];
    int p=1;
    for(int i=0;i=min;j--)
    System.out.print(a[i][j]+"\t");

    for(i=i-1,j=j+1;i>=min+1;i--)
    System.out.print(a[i][j]+"\t");

    if(n==0)
    System.exit(0);
    else
    abc(i+1,j+1,n-1,min+1);
    }
    }

    ReplyDelete
  11. #include
    #include
    main()
    {
    int i,j,b,n,c,d,l,s,f;
    n=5;
    int a[n][n];
    printf("\n Matrix is");
    for(i=0;i0)
    {
    i=n-b;
    for(j=(n-b);j<(n-f);j++)
    {
    printf("%d\t",a[i][j]);
    }
    l=l-1;
    if(l>0)
    j=n-d;
    for(i=d;i<(n-f);i++)
    {
    printf("%d\t",a[i][j]);
    }
    l=l-1;
    if(l>0)
    i=n-d;
    for(j=(n-s);j>=(n-b);j--)
    {
    printf("%d\t",a[i][j]);
    }
    l=l-1;
    if(l>0)
    j=n-b;
    for(i=n-s;i>n-b;i--)
    {
    printf("%d\t",a[i][j]);
    }
    l=l-1;
    d=d+1;
    c=c-1;
    s=s+1;
    b=b-1;
    f=f+1;
    }
    getch();
    }

    ReplyDelete
  12. //Himanshu Negi @ himanshunegi1987@gmail.com
    #include
    #include
    void func(int a[][4],int,int,int,int);
    void main(void)
    {
    clrscr();
    int a[5][4] = {
    {1,2,3,4},
    {5,6,7,8},
    {9,10,11,12},
    {13,14,15,16},
    {17,18,19,20}
    };

    func(a,0,0,4,3);
    getch();
    }

    void func( int a[][4],int x,int y,int x1,int y1)
    {
    for(int i=x,j=y;j<=y1;j++)
    {
    cout<<" "<=y;j--)
    {
    cout<<" "<x;i--)
    {
    cout<<" "<0)
    func(a,x,y,x1,y1);
    }

    ReplyDelete
  13. Following site has a complete java code.
    This solution works as follows
    1. print from top left to right top
    2. print from right top to right bottom
    3. print from right bottom to left bottom
    4. print from left bottom to left top
    then call the recursive function for inner layer continue till layer=min(rows,cols)/2
    http://www.dsalgo.com/2013/02/PrintMatrixSpiral.php.html

    ReplyDelete
  14. #include
    #include
    int main()
    {
    int m,n,i,j;
    int **a;
    scanf("%d%d",&m,&n);
    a=(int**)malloc(sizeof(int*)*n);
    for(i=0;i=0;j--)
    {
    printf("%d ",a[i][j]);
    }
    printf("\n");
    }
    return 0;
    }

    ReplyDelete