Traversal Patterns

Spiral Order

Walk the border of the matrix (right → down → left → up), then shrink the boundaries inward and repeat. Use four boundary variables: top, bottom, left, right. Shrink after each edge walk.

O(m*n)

O(1)

How It Works

Spiral traversal walks the outer border of the matrix in a fixed cycle — left to right along the top row, top to bottom down the right column, right to left along the bottom row, bottom to top up the left column — then shrinks inward and repeats. Four boundary variables (top, bottom, left, right) track the current unvisited frame; after finishing an edge, the corresponding boundary moves inward by one.

The boundaries make the logic clean: each element is visited exactly once, so the traversal is O(m*n) time with O(1) extra space beyond the output. The classic pitfall is the final partial layer — when only a single row or column remains, the left-going and up-going passes must be guarded so they do not revisit cells already emitted.

Step-by-Step Visualization

3x3 matrix spiral: right along top row

Output[1,2,3]

1/4

Code

Java

static List<Integer> spiralOrder(int[][] matrix) {
  List<Integer> result = new ArrayList<>();
  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++) result.add(matrix[top][i]);
    top++;
    for (int i = top; i <= bottom; i++) result.add(matrix[i][right]);
    right--;
    if (top <= bottom) for (int i = right; i >= left; i--) result.add(matrix[bottom][i]);
    bottom--;
    if (left <= right) for (int i = bottom; i >= top; i--) result.add(matrix[i][left]);
    left++;
  }
  return result;
}

Tips & Gotchas

1Maintain four boundaries: top, bottom, left, right

2After traversing each direction, shrink the corresponding boundary

3Stop when boundaries cross each other

Practice Problems

1Spiral Matrix
2Spiral Matrix II
3Rotate Image

About the Traversal Patterns Pattern

Navigate a 2D grid in non-standard orders. The key is maintaining boundaries or using mathematical relationships between coordinates to determine the traversal path.

Key insight

For traversal: use direction arrays dx=[0,0,1,-1], dy=[1,-1,0,0]. For sorted matrix search, start from top-right corner. For grid DP, fill row by row — current cell depends on top and left.

Common Matrix Interview Problems

Spiral Matrix
Rotate Image
Search a 2D Matrix
Number of Islands
Maximal Square
Set Matrix Zeroes
Word Search

Frequently Asked Questions

How do I avoid double-visiting cells in a spiral traversal?

Check the boundary conditions before the third and fourth edges. After walking the top row and right column, verify that top <= bottom before walking the bottom row, and left <= right before walking the left column. Without these guards, a single remaining row or column gets traversed twice.

Is there an alternative to the four-boundary approach?

Yes — direction simulation. Keep a direction vector, step forward until you would leave the grid or hit a visited cell, then turn clockwise. It uses O(m*n) extra space for the visited set (or mutates the input), whereas the boundary method needs only four integers.