Print matrix in spiral order

Problem statement – Given a 2D array (or matrix) of N rows and M columns, print it in a spiral order. Example, for the below matrix –

int[] arr = {
                {1, 2, 3},
                {4, 5, 6},
                {7, 8, 9},
            };

The output is –

1 2 3 6 9 8 7 4 5

Solution – When an interviewer asks you this question, he/she is just testing your implementation skills. This question isn’t tough because it doesn’t have any corner cases, but it is quite tough to solve if you start over thinking.

Let us label the rows/columns which we must print –

Print matrix in spiral order Theory of ProgrammingSo, our top-most row is top, bottom-most row is bottom, left-most column is left and right-most column is right. As we keep printing elements of the matrix, we will bring them closer to each other. Initially –

  • top = 0
  • right = M – 1
  • bottom  = N – 1
  • left = 0

As per the arrow indication, in our top row, we will print elements from left to right. So the loop to print it will look something like –

for (int i = left; i <= right; ++i) {
    print arr[top][i];
}

++top;

As you have noticed, the ++top is to bring it towards the center. Similarly, for printing the right column –

for (int i = top; i <= bottom; ++i) {
    print arr[i][right];
}

--right;

Similarly, for printing the bottom row –

for (int i = right; i >= left; --i) {
    print arr[bottom][i];
}

--bottom;

Similarly, for printing the left column –

for (int i = bottom; i >= top; --i) {
    print arr[i][left];
}

++left;

Now all that’s left is to execute this printing in a proper order. We could have a control variable dir, which denotes the direction. If –

  • dir == 1, print top row
  • dir == 2, print right column
  • dir == 3, print bottom row
  • dir == 4, print left column

We must keep rotating the value of dir between 1, 2, 3, 4 as long as top ≤ bottom and left ≤ right. If you have understood the logic, you should be able to write the code easily. If you didn’t just go through the explanation once more, it is can be tricky 😛

Code

public static void printInSpiralOrder(final int[][] arr) {
    if (arr.length == 0 || arr[0].length == 0) {
        return;
    }

    int top = 0, bottom = arr.length - 1, left = 0, right = arr[0].length - 1;
    int dir = 1;

    while (top <= bottom && left <= right) {
        if (dir == 1) {    // left-right
            for (int i = left; i <= right; ++i) {
                System.out.print(arr[top][i] + " ");
            }

            ++top;
            dir = 2;
        } else if (dir == 2) {     // top-bottom
            for (int i = top; i <= bottom; ++i) {
                System.out.print(arr[i][right] + " ");
            }

            --right;
            dir = 3;
        } else if (dir == 3) {     // right-left
            for (int i = right; i >= left; --i) {
                System.out.print(arr[bottom][i] + " ");
            }

            --bottom;
            dir = 4;
        } else if (dir == 4) {     // bottom-up
            for (int i = bottom; i >= top; --i) {
                System.out.print(arr[i][left] + " ");
            }

            ++left;
            dir = 1;
        }
    }
}

Keep practicing! Happy Coding! 😀

Leave a Reply