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);
	}
}
About these ads

2 Responses to Spiral Order, Java

  1. Indranil Das says:

    please give the code in java to accept numbers in M*N matrix in spiral way

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: