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)

say this out loud

I keep four boundaries and shrink them after each pass. The one thing to guard is the middle row or column on the final lap, or it gets emitted twice.

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

3 by 3 matrix, to be read in a spiral from the outside in

outputempty

1/9

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.