ISC Practicals and Theory - Spiral Traversal and Fill

This program fills a square matrix with the numbers 1, 2, 3, ... up to n x n in a clockwise spiral that starts at the top-left corner, prints the matrix, and then reads the same matrix back in spiral order. Only loops and a two-dimensional array are used, and everything is written in the main method.

Definition

A spiral order visits the outermost ring of a matrix first: along the top row from left to right, down the right column, along the bottom row from right to left and up the left column. It then repeats the same walk on the next inner ring, until every element has been visited once.

For $n = 3$ the spiral fill gives:

Reading this matrix in spiral order gives 1 2 3 4 5 6 7 8 9. Because the matrix was filled in the same order, the traversal always prints 1 to $n \times n$ in sequence. This also proves that the fill and the traversal agree.

Algorithm

1. Read the order n. If it is not from 2 to 10, print INVALID INPUT and stop.
2. Create the array a of order n. Keep four boundaries: top and bottom (the first and last row not yet filled) and left and right (the first and last column not yet filled), and the next number v = 1.
3. While top <= bottom and left <= right, walk one full turn of the spiral:
   • fill the top row from left to right, then top++;
   • fill the right column from top to bottom, then right--;
   • if top <= bottom, fill the bottom row from right to left, then bottom--;
   • if left <= right, fill the left column from bottom to top, then left++.

The two if tests stop an odd-sized matrix from being filled twice in the middle.

1. Print the matrix.
2. Reset the four boundaries and walk the spiral again in the same way, but print the elements instead of storing numbers. Print the spiral order.

Program

Everything is written inside main: the first while loop fills the matrix in a spiral, and the second while loop, with the same four boundaries, reads it back in spiral order.

import java.util.Scanner;

/* Program Spiral fills a square matrix with 1, 2, 3, ... in a clockwise
   spiral (starting at the top-left corner) and then reads the matrix back
   in spiral order. */
public class Spiral
{
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter n (2 to 10): ");
        int n = sc.nextInt();                    // order of the square matrix (number of rows = number of columns)
        if (n >= 2 && n <= 10)
        {
            int a[][] = new int[n][n];           // the n x n matrix
            int top = 0, bottom = n - 1;         // first and last row not yet filled
            int left = 0, right = n - 1;         // first and last column not yet filled
            int v = 1;                           // next number to be stored
            while (top <= bottom && left <= right)
            {
                for (int j = left; j <= right; j++)      // top row, left to right
                    a[top][j] = v++;
                top++;
                for (int i = top; i <= bottom; i++)      // right column, top to bottom
                    a[i][right] = v++;
                right--;
                if (top <= bottom)                       // bottom row, right to left
                {
                    for (int j = right; j >= left; j--)
                        a[bottom][j] = v++;
                    bottom--;
                }
                if (left <= right)                       // left column, bottom to top
                {
                    for (int i = bottom; i >= top; i--)
                        a[i][left] = v++;
                    left++;
                }
            }
            System.out.println("Spiral matrix:");
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                    System.out.print(a[i][j] + "\t");
                System.out.println();
            }
            top = 0;                             // the same four boundaries are used again to read the matrix
            bottom = n - 1;
            left = 0;
            right = n - 1;
            System.out.print("Spiral order: ");
            while (top <= bottom && left <= right)
            {
                for (int j = left; j <= right; j++)
                    System.out.print(a[top][j] + " ");
                top++;
                for (int i = top; i <= bottom; i++)
                    System.out.print(a[i][right] + " ");
                right--;
                if (top <= bottom)
                {
                    for (int j = right; j >= left; j--)
                        System.out.print(a[bottom][j] + " ");
                    bottom--;
                }
                if (left <= right)
                {
                    for (int i = bottom; i >= top; i--)
                        System.out.print(a[i][left] + " ");
                    left++;
                }
            }
            System.out.println();
        }
        else
            System.out.println("INVALID INPUT");
    }
}

Variable description table

Sample input and output

Enter n (2 to 10): 4
Spiral matrix:
1	2	3	4	
12	13	14	5	
11	16	15	6	
10	9	8	7	
Spiral order: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 

Enter n (2 to 10): 5
Spiral matrix:
1	2	3	4	5	
16	17	18	19	6	
15	24	25	20	7	
14	23	22	21	8	
13	12	11	10	9	
Spiral order: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 

Enter n (2 to 10): 2
Spiral matrix:
1	2	
4	3	
Spiral order: 1 2 3 4 

Enter n (2 to 10): 11
INVALID INPUT

Dry run

Take $n = 2$, the third sample. At the start top = 0, bottom = 1, left = 0, right = 1, v = 1.

Now top = 1 is greater than bottom = 0, so the while loop ends. The matrix is 1 2 and 4 3. The second while loop follows the same walks and prints 1 2 3 4, the same as the real run above.

Variations

1. Anticlockwise spiral "Fill an n x n matrix with 1 to n x n in an anticlockwise spiral and display it."
2. Spiral order of a given matrix "Accept an m x n matrix and print its elements in spiral order."
3. Boundary elements "Print the boundary elements of a matrix and find their sum."
4. Snake pattern "Fill an n x n matrix with 1 to n x n so that alternate rows run left to right and right to left."