Given a 2-dimensional array of integers, print the 2D array in spiral order.

For example:

A = [1,  2,  3,  4,
     5,  6,  7,  8,
     9,  10, 11, 12,
     13, 14, 15, 16]

Then spiral order output should be: [1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10].

We can notice that such spiral starts from (0,0) and traverse the edges of the (nxn) matrix with (0,0) as the top left corner and completes first round at just below the (0,0). Similarly, 2nd round continues from (1,1) and traverse edges of the (n-1)x(n-1) submatrix with (1,1) as the top left corner and completes the round just below (1,1).

That means for each round i, we traverse the a (n-i)x(n-i) submatrix with (i,i) as the top left corner as follows:

1. traverse the top row left to right from (i,i) to (i, n-i-1)
2. traverse the rightmost column down from (i+1, n-i-1) to (n-i-1, n-i-1) [note: we didn’t start from (i, n-i-1) as we have already traversed (i, n-i-1); similarly we didn’t finish at (n-i-1, n-i-1) as we will start the next step from there]
3. traverse the bottom row right to left from (n-i-1, n-i-1) to (n-i-1, i).
4. Traverse leftmost column up from (n-i-2, i) to (i+1, i).

Now, question is how many rounds to go? It depends on n. We can notice that each round i we are traversing a submatrix with (0,0) and (n-i-1, n-i-1) as the right diagonal corners. We are traversing two elements of the diagonal of the original matrix per round. So, no of rounds is n/2. If n is odd then the the middle element of the right diagonal should be left after n/2 rounds as described above.

Below is the implementation of the above idea. This is the optimal complexity i.e. O(n^2) time code for this problem.

void PrintSpiral(final int[][] input) {
    // assuming square matrix
    final int n = input.length;
    final StringBuilder sb = new StringBuilder();
    for (int i = 0; i < n / 2; i++) {
        for (int j = i; j < n - i; j++) {
            sb.append(input[i][j] + ", ");
        }
        for (int j = i + 1; j < n - i - 1; j++) {
            sb.append(input[j][n - i - 1] + ", ");
        }
        for (int j = n - i - 1; j >= i; j--) {
            sb.append(input[n - i - 1][j] + ", ");
        }
        for (int j = n - i - 2; j > i; j--) {
            sb.append(input[j][i] + ", ");
        }
    }

    if (n % 2 == 1) {
        sb.append(input[n / 2][n / 2]);
    }

    System.out.println(sb.toString());
}