Spiral Traversal of a matrix

Unraveling the Spiral: Traversing a Matrix Step-by-Step in Java

Matrix traversal is a fundamental concept in computer science, and one intriguing pattern is the spiral traversal. In this blog post, we'll dive deep into how to traverse a 2D matrix in a spiral order, providing step-by-step examples and a complete Java implementation.

Understanding Spiral Traversal

Imagine you're peeling the layers of an onion or tracing a spiral staircase. Spiral traversal involves visiting each element of a matrix in a clockwise spiral pattern, starting from the outermost elements and moving inwards.

Step-by-Step Examples

Let's illustrate the process with a couple of matrix examples.

Example 1: 3x3 Matrix

Matrix:
1 2 3
4 5 6
7 8 9

Step-by-Step Traversal:

1. Initialization:

   • top = 0, bottom = 2, left = 0, right = 2

   • ans = [] (an empty list to store the spiral order)

2. Top Row (Left to Right):

   • ans = [1, 2, 3]

   • top = 1

3. Right Column (Top to Bottom):

   • ans = [1, 2, 3, 6, 9]

   • right = 1

4. Bottom Row (Right to Left):

   • ans = [1, 2, 3, 6, 9, 8, 7]

   • bottom = 1

5. Left Column (Bottom to Top):

   • ans = [1, 2, 3, 6, 9, 8, 7, 4]

   • left = 1

6. Inner Layer (Middle Element):

   • ans = [1, 2, 3, 6, 9, 8, 7, 4, 5]

   • The while loop condition fails, and the loop terminates.

7. Result:

   • ans = [1, 2, 3, 6, 9, 8, 7, 4, 5]

Example 2: 3x5 Matrix

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

Step-by-Step Traversal:

1. Initialization:

   • top = 0, bottom = 2, left = 0, right = 4

   • ans = []

2. Top Row:

   • ans = [1, 2, 3, 10, 13]

   • top = 1

3. Right Column:

   • ans = [1, 2, 3, 10, 13, 14, 15]

   • right = 3

4. Bottom Row:

   • ans = [1, 2, 3, 10, 13, 14, 15, 12, 9, 8, 7]

   • bottom = 1

5. Left Column:

   • ans = [1, 2, 3, 10, 13, 14, 15, 12, 9, 8, 7, 4]

   • left = 1

6. Inner Layer (Top Row):

   • ans = [1, 2, 3, 10, 13, 14, 15, 12, 9, 8, 7, 4, 5, 6]

   • top = 2

7. Inner Layer (Right Column):

   • ans = [1, 2, 3, 10, 13, 14, 15, 12, 9, 8, 7, 4, 5, 6, 11]

   • right = 2

8. Bottom and left checks fail, and the loop terminates.

9. Result:

   • ans = [1, 2, 3, 10, 13, 14, 15, 12, 9, 8, 7, 4, 5, 6, 11]

Java Code Implementation

Java

package Arrays;

import java.util.ArrayList;
import java.util.List;

public class PrintSpiralMatrix {

    public static List<Integer> printSpiral(int num[][]) {
        List<Integer> ans = new ArrayList<Integer>();
        int m = num.length; // no of rows
        int n = num[0].length; // no of columns

        int top = 0, bottom = m - 1, left = 0, right = n - 1;

        while (top <= bottom && left <= right) {
            // Traverse top row
            for (int i = left; i <= right; i++) {
                ans.add(num[top][i]);
            }
            top++;

            // Traverse right column
            for (int i = top; i <= bottom; i++) {
                ans.add(num[i][right]);
            }
            right--;

            // Traverse bottom row (only if valid)
            if (top <= bottom) {
                for (int i = right; i >= left; i--) {
                    ans.add(num[bottom][i]);
                }
                bottom--;
            }

            // Traverse left column (only if valid)
            if (left <= right) {
                for (int i = bottom; i >= top; i--) {
                    ans.add(num[i][left]);
                }
                left++;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        int num[][] = {{1, 2, 3, 10, 13}, {4, 5, 6, 11, 14}, {7, 8, 9, 12, 15}};
        System.out.println(printSpiral(num));

        int num2[][] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        System.out.println(printSpiral(num2));

        int num3[][] = {{1,2},{3,4}};
        System.out.println(printSpiral(num3));

        int num4[][] = {{1}};
        System.out.println(printSpiral(num4));
    }
}

Key Improvements:

• Conditional Checks: The if (top <= bottom) and if (left <= right) checks prevent duplicate entries and handle matrices of various dimensions correctly.

• Clear Logic: The code follows the step-by-step traversal explained earlier, making it easy to understand.

• Examples: The main method includes various test cases, including rectangular and square matrices, to ensure the code's robustness.

This blog post provides a comprehensive guide to spiral matrix traversal, combining step-by-step examples with a robust Java implementation. Happy coding!