Spiral Matrix Traversal in DSA Java

Mental Model

We move around the edges of the matrix in a circle, peeling off one layer at a time until all elements are visited.

Analogy: Imagine peeling an onion layer by layer, starting from the outer skin and moving inward in a spiral path.

1 -> 2 -> 3 -> 4
↓           ↑
12         5
↓           ↑
11 10 9  8  6
↓           ↑
7 ←  6 ←  5 ← 4

Dry Run Walkthrough

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]

Goal: Print elements in spiral order: 1 -> 2 -> 3 -> 6 -> 9 -> 8 -> 7 -> 4 -> 5

Step 1: Traverse top row from left to right

Visited: 1 -> 2 -> 3
Remaining matrix edges to traverse

Why: Start from the top row to begin the spiral

Step 2: Traverse right column from top to bottom (excluding already visited top row)

Visited: 1 -> 2 -> 3 -> 6 -> 9
Remaining matrix edges to traverse

Why: Move down the right edge after top row

Step 3: Traverse bottom row from right to left (excluding already visited right column)

Visited: 1 -> 2 -> 3 -> 6 -> 9 -> 8 -> 7
Remaining matrix edges to traverse

Why: Move left along the bottom edge

Step 4: Traverse left column from bottom to top (excluding already visited bottom and top rows)

Visited: 1 -> 2 -> 3 -> 6 -> 9 -> 8 -> 7 -> 4
Remaining matrix edges to traverse

Why: Move up the left edge to complete the outer layer

Step 5: Move inward and traverse the remaining middle element

Visited: 1 -> 2 -> 3 -> 6 -> 9 -> 8 -> 7 -> 4 -> 5

Why: Complete the spiral by visiting the center

Result:

1 -> 2 -> 3 -> 6 -> 9 -> 8 -> 7 -> 4 -> 5

Annotated Code

DSA Java

import java.util.*;

public class SpiralMatrixTraversal {
    public static List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        if (matrix == null || matrix.length == 0) return result;

        int top = 0, bottom = matrix.length - 1;
        int left = 0, right = matrix[0].length - 1;

        while (top <= bottom && left <= right) {
            // Traverse from left to right on the top row
            for (int i = left; i <= right; i++) {
                result.add(matrix[top][i]);
            }
            top++;

            // Traverse from top to bottom on the right column
            for (int i = top; i <= bottom; i++) {
                result.add(matrix[i][right]);
            }
            right--;

            if (top <= bottom) {
                // Traverse from right to left on the bottom row
                for (int i = right; i >= left; i--) {
                    result.add(matrix[bottom][i]);
                }
                bottom--;
            }

            if (left <= right) {
                // Traverse from bottom to top on the left column
                for (int i = bottom; i >= top; i--) {
                    result.add(matrix[i][left]);
                }
                left++;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[][] matrix = {
            {1, 2, 3},
            {4, 5, 6},
            {7, 8, 9}
        };
        List<Integer> spiral = spiralOrder(matrix);
        for (int num : spiral) {
            System.out.print(num);
            if (num != spiral.get(spiral.size() - 1)) System.out.print(" -> ");
        }
        System.out.println();
    }
}

while (top <= bottom && left <= right) {

Continue spiral traversal while boundaries are valid

for (int i = left; i <= right; i++) { result.add(matrix[top][i]); }

Traverse top row left to right

top++;

Move top boundary down after traversing top row

for (int i = top; i <= bottom; i++) { result.add(matrix[i][right]); }

Traverse right column top to bottom

right--;

Move right boundary left after traversing right column

if (top <= bottom) { for (int i = right; i >= left; i--) { result.add(matrix[bottom][i]); } bottom--; }

Traverse bottom row right to left if still valid

if (left <= right) { for (int i = bottom; i >= top; i--) { result.add(matrix[i][left]); } left++; }

Traverse left column bottom to top if still valid

Output

1 -> 2 -> 3 -> 6 -> 9 -> 8 -> 7 -> 4 -> 5

Complexity Analysis

Time: O(m*n) because every element in the m by n matrix is visited exactly once

Space: O(m*n) for the output list storing all elements

vs Alternative: Compared to naive approaches that might revisit elements or use extra flags, this method efficiently uses boundary pointers to avoid repeated visits

Edge Cases

Empty matrix

Returns empty list without error

DSA Java

if (matrix == null || matrix.length == 0) return result;

Single row matrix

Traverses left to right only

DSA Java

while (top <= bottom && left <= right)

Single column matrix

Traverses top to bottom only

DSA Java

while (top <= bottom && left <= right)

When to Use This Pattern

When you need to visit all elements of a matrix in a circular, inward pattern, use spiral traversal with boundary pointers to peel layers.

Common Mistakes

Mistake: Not updating boundaries correctly causing infinite loops or repeated elements
Fix: After each edge traversal, update the corresponding boundary (top++, right--, bottom--, left++)

Mistake: Not checking boundary conditions before traversing bottom row or left column
Fix: Add checks like if (top <= bottom) and if (left <= right) before those traversals

Summary

Prints matrix elements in a spiral order starting from the top-left corner.

Use when you want to process matrix elements layer by layer in a circular pattern.

Keep track of four boundaries and move them inward after each edge traversal.

Practice

1. What is the main idea behind Spiral Matrix Traversal?

easy

A. Traverse the matrix in a circular pattern from outer to inner layers

B. Traverse the matrix row by row from top to bottom

C. Traverse the matrix column by column from left to right

D. Traverse only the diagonal elements of the matrix

Solution

1. Step 1: Understand traversal pattern

   Spiral traversal means moving around the edges of the matrix and gradually moving inward in a circular way.

2. Step 2: Compare options

   Only Traverse the matrix in a circular pattern from outer to inner layers describes moving in a circular pattern from outer to inner layers, which matches spiral traversal.

3. Final Answer:

   Traverse the matrix in a circular pattern from outer to inner layers -> Option A

4. Quick Check:

   Spiral traversal = circular outer to inner [OK]

Hint: Spiral means circle inward from edges [OK]

Common Mistakes:

• Confusing spiral with row-wise traversal
• Thinking spiral means diagonal only
• Mixing column-wise with spiral

2. Which of the following Java code snippets correctly initializes the boundaries for spiral traversal of a matrix int[][] matrix?

easy

A. int top = 1, bottom = matrix.length, left = 1, right = matrix[0].length;

B. int top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length - 1;

C. int top = 0, bottom = matrix[0].length - 1, left = 0, right = matrix.length - 1;

D. int top = matrix.length, bottom = 0, left = matrix[0].length, right = 0;

Solution

1. Step 1: Identify matrix dimensions

   For a 2D array, rows = matrix.length, columns = matrix[0].length.

2. Step 2: Set boundaries correctly

   Top and left start at 0, bottom is last row index (length-1), right is last column index (length-1). int top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length - 1; matches this.

3. Final Answer:

   int top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length - 1; -> Option B

4. Quick Check:

   Boundaries start at 0 and end at length-1 [OK]

Hint: Boundaries start at 0, end at length-1 [OK]

Common Mistakes:

• Using 1-based indices instead of 0-based
• Swapping rows and columns in boundaries
• Setting bottom or right greater than max index

3. What is the output of the following Java code snippet for spiral traversal?

int[][] matrix = {
  {1, 2, 3},
  {4, 5, 6},
  {7, 8, 9}
};

int top = 0, bottom = 2, left = 0, right = 2;

while (top <= bottom && left <= right) {
  for (int i = left; i <= right; i++) System.out.print(matrix[top][i] + " ");
  top++;
  for (int i = top; i <= bottom; i++) System.out.print(matrix[i][right] + " ");
  right--;
  if (top <= bottom) {
    for (int i = right; i >= left; i--) System.out.print(matrix[bottom][i] + " ");
    bottom--;
  }
  if (left <= right) {
    for (int i = bottom; i >= top; i--) System.out.print(matrix[i][left] + " ");
    left++;
  }
}

medium

A. 1 4 7 8 9 6 3 2 5

B. 1 2 3 4 5 6 7 8 9

C. 1 2 3 6 9 8 7 4 5

D. 9 8 7 6 5 4 3 2 1

Solution

1. Step 1: Trace first outer layer

   Top row: 1 2 3, right column down: 6 9, bottom row left: 8 7, left column up: 4

2. Step 2: Trace inner layer

   Now top=1, bottom=1, left=1, right=1, print center element: 5

3. Final Answer:

   1 2 3 6 9 8 7 4 5 -> Option C

4. Quick Check:

   Spiral order matches 1 2 3 6 9 8 7 4 5 [OK]

Hint: Follow boundaries and print edges inward [OK]

Common Mistakes:

• Printing rows or columns in wrong order
• Missing center element in odd-sized matrix
• Not updating boundaries correctly

4. Identify the bug in this spiral traversal code snippet:

int top = 0, bottom = matrix.length - 1;
int left = 0, right = matrix[0].length - 1;
while (top < bottom && left < right) {
  for (int i = left; i <= right; i++) System.out.print(matrix[top][i] + " ");
  top++;
  for (int i = top; i <= bottom; i++) System.out.print(matrix[i][right] + " ");
  right--;
  for (int i = right; i >= left; i--) System.out.print(matrix[bottom][i] + " ");
  bottom--;
  for (int i = bottom; i >= top; i--) System.out.print(matrix[i][left] + " ");
  left++;
}

medium

A. The while condition should use <= instead of < to include all layers

B. The for loops should use < instead of <= to avoid index errors

C. The boundaries are initialized incorrectly

D. The print statements should be inside if conditions to avoid duplicates

Solution

1. Step 1: Analyze while loop condition

   Using < excludes the case when top == bottom or left == right, missing last layer in odd-sized matrices.

2. Step 2: Correct condition to include all layers

   Changing to <= ensures the center or last layer is processed.

3. Final Answer:

   The while condition should use <= instead of < to include all layers -> Option A

4. Quick Check:

   Use <= in while to cover all layers [OK]

Hint: Use <= in while to cover all matrix layers [OK]

Common Mistakes:

• Using < excludes center element in odd matrices
• Not updating boundaries after each loop
• Missing if checks for inner loops

5. Given a rectangular matrix of size 3x4:

int[][] matrix = {
  {1, 2, 3, 4},
  {5, 6, 7, 8},
  {9, 10, 11, 12}
};

What is the spiral traversal output?

hard

A. 1 5 9 10 11 12 8 4 3 2 6 7

B. 1 2 3 4 8 12 11 10 9 5 7 6

C. 1 2 3 4 8 12 11 10 9 6 5 7

D. 1 2 3 4 8 12 11 10 9 5 6 7

Solution

1. Step 1: Traverse top row left to right

   Print 1 2 3 4

2. Step 2: Traverse right column top to bottom

   Print 8 12

3. Step 3: Traverse bottom row right to left

   Print 11 10 9

4. Step 4: Traverse left column bottom to top

   Print 5

5. Step 5: Traverse inner row left to right

   Print 6 7

6. Final Answer:

   1 2 3 4 8 12 11 10 9 5 6 7 -> Option D

7. Quick Check:

   Follow edges inward for rectangular matrix [OK]

Hint: Print edges clockwise, move inward layer by layer [OK]

Common Mistakes:

• Mixing order of inner elements
• Skipping last inner row
• Confusing left column traversal direction