ISC Practicals and Theory - Spiral Traversal and Fill (OOP)

This version writes the spiral fill and spiral traversal as a class Spiral with a parameterised constructor. The constructor receives the order of the matrix, and each method does one job: checking the order, setting the boundaries, filling, displaying and traversing the matrix. main reads n, creates the object and calls the methods.

Definition

A spiral order visits the outermost ring of a matrix first (top row left to right, right column downwards, bottom row right to left, left column upwards), then repeats the walk on the next inner ring. Filling a matrix with 1, 2, 3, ... n x n in this order gives, for $n = 3$:

Reading the filled matrix back in spiral order prints 1 2 3 4 5 6 7 8 9.

Algorithm

1. main reads num and creates new Spiral(num). The constructor stores it in n and creates the matrix a[n][n] only if isValid() is true.
2. isValid() returns true when n is from 2 to 10. If not, main prints INVALID INPUT.
3. resetBoundaries() sets top = 0, bottom = n - 1, left = 0, right = n - 1.
4. fill() calls resetBoundaries() and, with v starting at 1, repeats while top <= bottom and left <= right:
   • top row left to right, then top++;
   • right column top to bottom, then right--;
   • if top <= bottom, bottom row right to left, then bottom--;
   • if left <= right, left column bottom to top, then left++.
5. display() prints the matrix row by row.
6. traverse() calls resetBoundaries() and makes the same four walks, printing each element.

Program

The constructor prepares the matrix, isValid() checks the order, resetBoundaries() sets the four boundaries, fill() stores the numbers, display() prints the matrix and traverse() prints the spiral order.

import java.util.Scanner;

/* Class Spiral fills an n x n matrix with 1, 2, 3, ... n*n in a clockwise
   spiral (starting at the top-left corner) and then reads the matrix back
   in spiral order. */
public class Spiral
{
    int n;         // order of the square matrix
    int a[][];     // the n x n matrix
    int top;       // first row not yet visited
    int bottom;    // last row not yet visited
    int left;      // first column not yet visited
    int right;     // last column not yet visited

    /* Parameterised constructor. Parameter nn: the order of the matrix.
       It stores nn in n and creates the matrix only when n is valid. */
    Spiral(int nn)
    {
        n = nn;
        if (isValid())
            a = new int[n][n];
    }

    /* Returns true if n is from 2 to 10, otherwise false */
    boolean isValid()
    {
        return n >= 2 && n <= 10;
    }

    /* Sets the four boundaries to the outermost rows and columns */
    void resetBoundaries()
    {
        top = 0;
        bottom = n - 1;
        left = 0;
        right = n - 1;
    }

    /* Fills the matrix with 1, 2, 3, ... n*n in a clockwise spiral. */
    void fill()
    {
        int v = 1;                       // next number to be stored
        resetBoundaries();
        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++;
            }
        }
    }

    /* Prints the matrix row by row */
    void display()
    {
        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();
        }
    }

    /* Prints the elements of the matrix in clockwise spiral order */
    void traverse()
    {
        resetBoundaries();
        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();
    }

    /* main reads n, creates the object and calls the methods */
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter n (2 to 10): ");
        int num = sc.nextInt();           // order entered by the user
        Spiral ob = new Spiral(num);      // object of class Spiral
        if (ob.isValid())
        {
            ob.fill();
            ob.display();
            ob.traverse();
        }
        else
            System.out.println("INVALID INPUT");
    }
}

Variable description table

Sample input and output

Enter n (2 to 10): 3
Spiral matrix:
1	2	3	
8	9	4	
7	6	5	
Spiral order: 1 2 3 4 5 6 7 8 9 

Enter n (2 to 10): 6
Spiral matrix:
1	2	3	4	5	6	
20	21	22	23	24	7	
19	32	33	34	25	8	
18	31	36	35	26	9	
17	30	29	28	27	10	
16	15	14	13	12	11	
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 26 27 28 29 30 31 32 33 34 35 36 

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

Enter n (2 to 10): 1
INVALID INPUT

Dry run

Take $n = 3$, the first sample. resetBoundaries() gives top = 0, bottom = 2, left = 0, right = 2, and v = 1.

Now top = 2 > bottom = 1, so the loop ends. The matrix is 1 2 3, 8 9 4, 7 6 5, and traverse() prints 1 2 3 4 5 6 7 8 9, 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."