Spiral Order, Java

This is a problem I’ve heard mentioned but never really had a reason to look into. As they say, the science is gone from computer science. I sat down today and put some thought into it.

Spiral order is what you’d think. Given a 2D array, you move from left to right, top to bottom, right to left, and bottom to top printing out the values in order. For example,

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

The spiral order of this matrix is,

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

The algorithm to walk in spiral order works nicely with recursion. You recursively, “peel” off the top, right, bottom, left portions of the matrix until there’s nothing left. For example (forgive the ASCII art), peel off the top,

  1 2 3 4

  5  6  7  8
  9 10 11 12
 13 14 15 16

peel off the right,

  5  6  7     8
  9 10 11    12
 13 14 15    16

peel off the bottom,

  5  6  7
  9 10 11 

 13 14 15

peel off the left,

 5     6  7
 9    10 11

peel off the top (again, starting over here),

 6 7

 10 11

peel the right again,

 10    11

and finally, one more peel of the bottom gets the last element,

 10

and we are done.

The code is below. spiralOrderR() implements the recursive algorithm. It calls peelTop(), which calls peelLeft(), which calls peelBottom(),which calls peelLeft(), and so on, until it’s done.  The peeling happens in the arguments to the recursive call, where the bounds of the matrix are reduced as appropriate at each pass.

public class SpiralOrder {
	public static <T> List<T> spiralOrderR(T[][] matrix) {
		int startx = 0;
		int starty = 0;
		int endx = matrix.length - 1;
		int endy = matrix.length - 1;

		List<T> spiral = new ArrayList<T>();

		peelTopRight(matrix, startx, endx, starty, endy, spiral);
		return spiral;
	}

	private static <T> void peelTop(T[][] matrix, int startx, int endx, int starty, int endy, List<T> spiral) {
		if (startx > matrix.length / 2) {
			return;
		}
		for (int i = startx; i <= endx; i++) {
			spiral.add(matrix[i][starty]);
		}
		peelRight(matrix, startx, endx, starty+1, endy, spiral);
	}

	private static <T> void peelRight(T[][] matrix, int startx, int endx, int starty, int endy, List<T> spiral) {
		for (int i = starty; i <= endy; i++) {
			spiral.add(matrix[endx][i]);
		}
		peelBottom(matrix, startx, endx-1, starty, endy, spiral);
	}

	private static <T> void peelBottom(T[][] matrix, int startx, int endx, int starty, int endy, List<T> spiral) {
		for (int i = endx; i >= startx; i--) {
			spiral.add(matrix[i][endy]);
		}
		peelLeft(matrix, startx, endx, starty, endy-1, spiral);
	}

	private static <T> void peelLeft(T[][] matrix, int startx, int endx, int starty, int endy, List<T> spiral) {
		for (int i = endy; i >= starty; i--) {
			spiral.add(matrix[startx][i]);
		}
		peelTop(matrix, startx+1, endx, starty, endy, spiral);
	}

	public static void main(String[] args) {
		Integer[][] ints = new Integer[5][5];
		int count = 1;
		for (int i = 0; i < ints.length; i++) {
			for (int j = 0; j < ints[i].length; j++) {
				ints[j][i] = count++;
			}
		}

		List<Integer> spiral = spiralOrder(ints);
		System.out.println(spiral);
		spiral = spiralOrderR(ints);
		System.out.println(spiral);
	}
}