Traversal Patterns

Diagonal Traversal

Elements on the same diagonal share a common property: i+j is constant (one direction) or i-j is constant (the other). Group by this key to traverse diagonals. Alternate direction for zigzag.

O(m*n)

say this out loud

Cells on a diagonal share the same row plus column sum, so I group by that and reverse alternate groups for the zigzag.

How It Works

Every anti-diagonal of a matrix shares one invariant: the sum i+j of the row and column indices is constant along it. Diagonals running the other way share a constant difference i-j. Grouping cells by that key lets you traverse or bucket every diagonal without any special path-walking logic, just iterate the grid once and append each element to the list for its key.

For zigzag output (as in Diagonal Traverse), alternate the direction per diagonal: when i+j is even, reverse the collected order so the walk goes up-right, otherwise keep it down-left. One pass over m*n cells gives O(m*n) time; the hash-of-lists variant uses O(m*n) space, while an index-arithmetic version that computes each next cell directly runs in O(1) extra space.

Step-by-Step Visualization

Read the same matrix diagonally, alternating direction on each diagonal

outputempty

1/8

Code

Java

static int[] findDiagonalOrder(int[][] mat) {
  int m = mat.length, n = mat[0].length;
  List<Integer> result = new ArrayList<>();
  Map<Integer, List<Integer>> diags = new TreeMap<>();

  for (int i = 0; i < m; i++)
    for (int j = 0; j < n; j++) {
      diags.computeIfAbsent(i + j, k -> new ArrayList<>()).add(mat[i][j]);
    }

  for (Map.Entry<Integer, List<Integer>> e : diags.entrySet()) {
    List<Integer> vals = e.getValue();
    if (e.getKey() % 2 == 0) Collections.reverse(vals);
    result.addAll(vals);
  }
  return result.stream().mapToInt(Integer::intValue).toArray();
}

Tips & Gotchas

1Elements on the same diagonal have the same i+j (or i-j) value

2Group elements by their diagonal index for diagonal traversal

3Alternate direction for zigzag traversal

Practice Problems

1Diagonal Traverse
2Diagonal Traverse II
3Sort the Matrix Diagonally

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

When should I group by i+j versus i-j?

Use i+j for anti-diagonals that run from top-right to bottom-left. The sum stays constant as one index rises while the other falls. Use i-j (or j-i) for main-direction diagonals running top-left to bottom-right, where both indices increase together. Pick whichever matches the diagonals the problem describes.

How does this help with sorting each diagonal of a matrix?

Bucket every element under its i-j key, sort each bucket independently, then write the sorted values back along the same diagonals. This turns a 2D geometric problem into a handful of 1D sorts, costing O(m*n log(min(m,n))) overall.