Print a square matrix in Spiral order

For example, consider a 4x4 matrix:

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

The spiral order is: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Given a matrix of order mxm, the problem can be solved using a divide and conquer technique as:

Step 1: Print the outermost elements of the 4x4 matrix by visiting the elements in a

            top –> right –> bottom –> left –> up manner.

1	2	3	4
12			5
11			6
10	9	8	7

The remaining matrix is of order 2x2.

Step 2: Print the outermost elements of the 2x2 matrix by visiting the elements in a

            top –> right –> bottom –> left –> up manner.

13	14
16	15

There are no more elements in the matrix, we are done.

In general, a problem of size mxm can be divided into (m-2)x(m-2) at each step, until 2x2 or a 1x1 matrix is got. As all the elements in the matrix are visited exactly once, the complexity of this algorithm is O(mxm).

Here is the C++ code:

void PrintSpiralMatrix(int row_start, int row_end, int col_start, int col_end) {

  if(row_start > row_end || col_start > col_end) {

    return;

  }

  if(col_end >= col_start) {

    // print the first row

    for(int i = col_start; i <= col_end; ++i) {

      cout << input[row_start][i] << " ";

    }

    // print the last column

    for(int j = row_start+1; j <= row_end; ++j) {

      cout << input[j][col_end] << " ";

    }

    // print the last row

    for(int i = col_end-1; i >= col_start; --i) {

      cout << input[row_end][i] << " ";

    }

    // print the first column

    for(int j = row_end-1; j > row_start; --j) {

      cout << input[j][col_start] << " ";

    }

  }

PrintSpiralMatrix(row_start+1, row_end-1, col_start+1, col_end-1);

}

Here is the non-recursive version:

void PrintSpiralSquareMatrix(int row_start, int row_end, int col_start, int col_end) {

  while(col_end >= col_start && row_end >= row_start && col_end >= col_start) {

    // print the first row

    for(int i = col_start; i <= col_end; ++i) {

      cout << input[row_start][i] << " ";

    }

    // print the last column

    for(int j = row_start+1; j <= row_end; ++j) {

      cout << input[j][col_end] << " ";

    }

    // print the last row

    for(int i = col_end-1; i >= col_start; --i) {

      cout << input[row_end][i] << " ";

    }

    // print the first column

    for(int j = row_end-1; j > row_start; --j) {

      cout << input[j][col_start] << " ";

    }

    ++row_start, --row_end;

    ++col_start, --col_end;

  }

}

Invoke the function as PrintSpiralMatrix(0,3,0,3) and PrintSpiralSquareMatrix(0,3,0,3) for the example matrix.