CC-7 : Output elements of matrix using Spiral traversal.

Description:

A matrix can be visualized as a set of concentric rectangles. In the matrix below, elements 1,2,3,4,8,12,16,15,14,13,9,5 represent the outermost rectangle. The elements 6,7,11,10 represent an inner rectangle in the matrix. While doing spiral traversal, we need to traverse the outermost rectangle in a spiral manner from top left to top right, from top right to bottom right, from bottom right to bottom left and bottom left to top right (note corner elements like top right will be traversed only once in each spiral traversal). After this we will traverse the inner rectangles in a similar spiral fashion till all elements are traversed. Given input matrix mat, we need to traverse it spirally and output the elements that were traversed.

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

Outer most rectangle top element=1, right element=4, bottom element=16, left element=13
Inner rectangle top element=6, right element=7, bottom element=11, left element=10

Test cases and expected outputs:

Input1	Expected outputs
mat = { {1,2,3}, {4,5,6}, {7,8,9} }	Spiral traversal: 1,2,3,6,9,8,7,4,5
mat= { 55,66,77,88}, {11,22,33,44}, {99,109,119,129} }	Spiral traversal: 55,66,77,88,44,129,119,109,99,11,22,33
mat={ {30,40}, {50,60}, {70,80}, {90,100}}	Spiral traversal: 30,40,60,80,100,90,70,50
mat = { {1,2,3,4}, {5,6,7,8}, {9,10,11,12}, {13,14,15,16}};	Spiral traversal: 1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10

Pseudocode:

The java method should accept following input parameters: mat (integer matrix).

Initialize an array named spiral to hold the result of the spiral traversal. The size of the spiral array should be the same as the number of elements of the input matrix.

Initialize variable sIdx to hold the current index of spiral array while it is being populated.

Similarly, initialize another variable idx to hold the current index of mat while it is being traversed.

Initialize 4 variables top, right, bottom, left to hold the indexes of the outermost rectangle of input matrix. Variable top should be set to 0. Variable right should be set to mat[0].length-1; Variable bottom should be set to mat.length-1. Variable left should be set to 0.

Keep repeating below steps using a while loop till we have traversed the innermost rectangle of the matrix:

Set idx variable’s value equal to left. Do a row traversal of current rectangle from top to right, by incrementing idx variable for column index, and store element at each index in spiral array. At end of top to right traversal increment top variable by 1.

Set idx variable’s value equal to top. Do a column traversal the elements from right to bottom, incrementing the idx variable for row index, and store element at each index in spiral array. Note since the rightmost element has already been stored in spiral matrix in previous step, it should not be stored again. At end of right to bottom traversal, decrement right variable by 1.

Set idx variable’s value equal to right. Do a reverse row traversal from bottom to left, decrementing idx variable for column index, and store element at each index in spiral array. Note that

Since the bottom element has already been stored in spiral matrix in previous step, it should not be stored again. At end of bottom to left traversal, decrement bottom variable by 1.

Set idx variable’s value equal to bottom. Next do a column traversal from left to top, decrementing idx variable for column index, and store element at each index in spiral array. Note since the left and top elements have already been stored in spiral matrix in previous step, the same should not be stored again. At end of left to top traversal, increment left variable by 1.

After above loops are complete, return spiral array.

Code:

public int[]  matArraySpiralTraversal(int[][] mat) throws Exception{
	int[] spiral=new int[(mat.length) * (mat[0].length)];
	int sIdx=0; int idx;
	int top=0; int left=0; int bottom=mat.length-1; int right=mat[0].length-1;
	while ((top<=bottom)&&(left<=right)) {
		idx=left;
		while (idx <= right) {
			spiral[sIdx]=mat[top][idx];
			idx++;
			sIdx++;
		}
		top++;
		idx=top;
		while (idx <= bottom) {
			spiral[sIdx]=mat[idx][right];
			idx++;
			sIdx++;
		}
		right--;
		idx=right;
		if (top<=bottom) {
			while (idx >= left) {
				spiral[sIdx]=mat[bottom][idx];
				idx--;
				sIdx++;
			}
		bottom--;
		}
		if (left<=right) {
			idx=bottom;
			while (idx >= top) {
				spiral[sIdx]=mat[idx][left];
				idx--;
				sIdx++;
			}
		left++;
		}			
	}
	return spiral;
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

public class MdArraySpiralTraversal {
	
public int[]  matArraySpiralTraversal(int[][] mat) throws Exception{
	int[] spiral=new int[(mat.length) * (mat[0].length)];
	int sIdx=0; int idx;
	int top=0; int left=0; int bottom=mat.length-1; int right=mat[0].length-1;
	while ((top<=bottom)&&(left<=right)) {
		idx=left;
		while (idx <= right) {
			spiral[sIdx]=mat[top][idx];
			idx++;
			sIdx++;
		}
		top++;
		idx=top;
		while (idx <= bottom) {
			spiral[sIdx]=mat[idx][right];
			idx++;
			sIdx++;
		}
		right--;
		idx=right;
		if (top<=bottom) {
			while (idx >= left) {
				spiral[sIdx]=mat[bottom][idx];
				idx--;
				sIdx++;
			}
		bottom--;
		}
		if (left<=right) {
			idx=bottom;
			while (idx >= top) {
				spiral[sIdx]=mat[idx][left];
				idx--;
				sIdx++;
			}
		left++;
		}			
	}
	return spiral;
}
	
public static void main(String[] args) {
	MdArraySpiralTraversal ap=new MdArraySpiralTraversal();
	int ret[];
	try {
	int[][] arr = {	{1,2,3},
					{4,5,6},	
					{7,8,9}
	};
	print2dArray(arr, "The 2d Array");
	ret=ap.matArraySpiralTraversal(arr);
	printArraySummary(ret, "Spiral traversal");
	
	int[][] arr1 = {	{55,66,77,88},
						{11,22,33,44},	
						{99,109,119,129},
	};
	print2dArray(arr1, "The 2d Array");
	ret=ap.matArraySpiralTraversal(arr1);
	printArraySummary(ret, "Spiral traversal");
	
			
	int[][] arr2 = 	{	{30,40},
						{50,60},	
						{70,80},
						{90,100}								
	};
	print2dArray(arr2, "The 2d Array");
	ret=ap.matArraySpiralTraversal(arr2);
	printArraySummary(ret, "Spiral traversal");
			
	int[][] arr3 = {	{1,2,3,4},
						{5,6,7,8},	
						{9,10,11,12},
						{13,14,15,16}
	};
	print2dArray(arr3, "The 2d Array");
	ret=ap.matArraySpiralTraversal(arr3);
	printArraySummary(ret, "Spiral traversal");
			
			
	}catch (Exception exception) {
	System.out.print("Exception,"+ exception);
	exception.printStackTrace();
				
	}
}
			
public static void print2dArray(int[][] intArray, String label) throws Exception {
   	// Case 1: The input Array is null !!
	if (intArray == null) { System.out.println("\n\n Input 2d Array was null !! \n"); return; }
	// Case 2: Print input Array by index (first to last)
	System.out.println();
	System.out.println("*********************************************************************");
	System.out.print(label+" : \n");
	int rIdx=0; int cIdx=0;
	for (rIdx=0; rIdx < intArray.length; rIdx++) {
		for (cIdx=0; cIdx < intArray[rIdx].length; cIdx++) {
			System.out.print(intArray[rIdx][cIdx]);
			if (cIdx < intArray[rIdx].length) System.out.print(",");
		}
		System.out.print("\n");
	} 
	System.out.println();
	System.out.println("**********************************************************************");
	System.out.println();
	Thread.sleep(2000);
	return;	
}

public static void printArraySummary(int[] intArray, String label) throws Exception {
   	// Case 1: The input Array is null !!
	if (intArray == null) { System.out.println("\n\n Input Array was null !! \n"); return; }
	// Case 2: Print input Array by index (first to last)
	System.out.println();
	System.out.println("************************************************************************");
	System.out.print(label+" : ");
	int arrayIndex=0;
	for (arrayIndex=0; arrayIndex < intArray.length; arrayIndex++) {
			System.out.print(intArray[arrayIndex]);
			if (arrayIndex< intArray.length-1) {System.out.print(",");}
	} 
	System.out.println();
	System.out.println("*************************************************************************");
	System.out.println();
	Thread.sleep(2000);
	return;
}				
			

}