Wednesday, June 11, 2014

Spiral Traversal of 2 dimensional Array

I would like to share this interesting question which is asked in data structures and algorithms round in some companies:

Problem: How would you traverse a two dimensional array in spiral fashion.


package com.girish.algorithms;

public class SpiralTraversal {


static int ROW_SIZE = 5;
static int COLUMN_SIZE = 6;
static int COLUMNS_TILL_RIGHT=5;
static int ROWS_TILL_DOWN=4;
static int COLUMNS_TILL_LEFT=0;
static int ROWS_TILL_UP=0;
static int[][] Array = new int[][]
{ {1, 2, 3, 4, 5, 6},
{7, 8, 9, 10, 11, 12},
{13, 14, 15, 16, 17, 18},
{19, 20, 21, 22, 23, 24},
{25, 26, 27, 28, 29, 30} };

public static void traverse(int m, int n, boolean directionUp)
{

System.out.println("{"+m+", "+n+"} "+ Array[m][ n]);
// Recurse right
if ((n+1<=COLUMNS_TILL_RIGHT) && !directionUp)
{
traverse(m, n+1, false);
return;
}
// Recurse down

if ((m+1<=ROWS_TILL_DOWN) && !directionUp)
{
traverse(m+1, n, false);
return;
}
// Recurse Left
if ((m > 0 && n >0) && (n-1>COLUMNS_TILL_LEFT))
{
traverse(m, n-1, true);
return;
}
//Recurse up
if ((m > 0) && (m-1>ROWS_TILL_UP))
{
traverse(m-1, n, true);
return;
}
COLUMNS_TILL_RIGHT--;
ROWS_TILL_DOWN--;
COLUMNS_TILL_LEFT++;
ROWS_TILL_UP++;
if ((COLUMNS_TILL_LEFT < COLUMNS_TILL_RIGHT) || (ROWS_TILL_DOWN > ROWS_TILL_UP))
{
traverse (m, n+1, false);
}
}

public static void main(String[] args) {
traverse(0, 0, false);

}

}