Monday, November 11, 2013

Printing the matrix in a spiral order

Given a two dimensional array or a matrix, how do we write a program to print the elements in a spiral order.

For example the spiral order for the following matrix is
1  2  3  4  8  12  16  15  14  13  9  5  6  7  11  10

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

The algorithm for this problem involves four steps. 
  • Print the elements of the top row from left to right and increment top.
  • Print the elements of right column from top to bottom and decrement right.
  • Print the elements of bottom tow from right to left and decrement bottom.
  • Print the elements of left column from bottom to top and increment left.
Repeat the above steps until there are no more elements left. 
As the algorithm indicates, we need four variables to keep track of the top and bottom rows, left and right columns. We also use an extra variable for the direction. It can have four values indicating four possible directions.

Here is the Java implementation of the above algorithm.