Sunday, June 28, 2015

Spiral Order Traversal of Two Dimensional Matrix - 1

Problem:

Given a two dimensional array, print the elements in spiral order starting at the top left corner.

Example:

Output:

1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10

Java Program:

public class SpiralOutToIn {
 public static void main(String[] args) {
  int [][] A = {{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}}; //m x n, m=n, m and n even 
  //int [][] A = {{1,2,3},{5,6,7},{9,10,11}}; //m x n, m=n, m and n odd
  //int [][] A = {{1,2,3,4},{5,6,7,8},{9,10,11,12}}; //m x n, m < n, m odd and n even
  //int [][] A = {{1,2,3,4,17},{5,6,7,8,18},{9,10,11,12,19},{13,14,15,16,20}}; //m x n, m < n, m even and n odd
  //int [][] A = {{1,2,3},{5,6,7},{9,10,11},{13,14,15}}; //m x n, m > n, m even and n odd
  //int [][] A = {{1,2,3,19},{5,6,7,20},{9,10,11,21},{13,14,15,22},{16,17,18,23}}; //m x n, m > n, m odd and n even
  //Boundary Value Test Cases
  //int [][] A = {{}};
  //int [][] A = {{1}};

  int layer = 0;
  //Go till half the length of the array.
  int maxLayer = A.length % 2 == 0 ? A.length/2 - 1 : A.length/2;
  while(layer <= maxLayer) {
   int i=layer;
   int j=layer;
   //Left to Right
   for(j=layer; j<=A[i].length-1-layer;j++) {
    System.out.print(A[i][j] + " ");
   }
   j = A[i].length - 1 -layer;
   //Top to Down
   for(i=layer + 1; i <= A.length - 1 - layer; i++) {
    System.out.print(A[i][j] + " ");
   }
   i = A.length - 1 - layer;
   //Right to Left
   for(j=A[i].length - 2 - layer; j >= layer; j--) {
    System.out.print(A[i][j] + " ");
   }
   j = layer;
   //Down to Top
   for(i=A.length - 2 - layer; i>=layer + 1; i--) {
    System.out.print(A[i][j] + " ");
   }
   layer++;
  }
 }
}