Diagonal Traverse

Given an m x n matrix, return its elements in diagonal order (zigzag). Diagonals are traversed alternating upward-right and downward-left.

Why this is worth learning

The sum r+c identifies a diagonal. Its parity determines traversal direction, separating geometry from boundary special cases.

Before coding: one-minute experiment

What diagonal order comes from [[1,2,3],[4,5,6]]?

Function signature

func FindDiagonalOrder(matrix [][]int) []int

Inputs / outputs

• matrix: 2D slice of integers.
• Return: slice of elements in diagonal order.

Example

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

Constraints

• 0 <= m, n <= 1000

Core idea (near-solution)

There are m+n-1 diagonals. For each diagonal index d = 0..m+n-2:

• An even diagonal starts at its bottom-left endpoint (left column or bottom row). An odd diagonal starts at its top-right endpoint (top row or rightmost column).
• If d is even, traverse upward-right; if odd, traverse downward-left.

Invariant: each element belongs to exactly one diagonal d = r + c.

Algorithm (step-by-step)

1. If matrix is empty, return empty.
2. For d from 0 to m+n-2:
   • If d is even: start at (r, c) = (min(d, m-1), d - min(d, m-1)) and move up-right.
   • If d is odd: start at (r, c) = (d - min(d, n-1), min(d, n-1)) and move down-left.
3. Append elements while indices are in bounds.

Correctness sketch

Every cell belongs to exactly one diagonal d=r+c between 0 and m+n-2. For even d, start at the largest valid row on that diagonal and repeatedly decrease row while increasing column; this visits it upward-right. For odd d, start at the largest valid column and walk downward-left. The chosen starting coordinate satisfies the bounds, and each step preserves r+c=d until the opposite boundary is reached. No cell can repeat across diagonals because its coordinate sum is unique, and the monotone walk visits every valid coordinate within a diagonal. Concatenating diagonals in increasing d yields the required zigzag order.

Trace (hand walkthrough)

Example input:
matrix = [
  [1,2,3],
  [4,5,6],
  [7,8,9]
]
Output: [1,2,4,7,5,3,6,8,9]

Walk:
- d=0: [1]
- d=1, odd: (0,1) -> (1,0), emit 2,4
- d=2, even: (2,0) -> (1,1) -> (0,2), emit 7,5,3
- d=3, odd: (1,2) -> (2,1), emit 6,8
- d=4, even: (2,2), emit 9
- concatenate: [1,2,4,7,5,3,6,8,9]

Pitfalls to avoid

• Incorrect start positions on edges.
• Forgetting to handle empty matrices.

Debugging lens

Use a wide rectangle and its tall counterpart. Mixing n with m in the starting coordinate can pass square cases. Check that output length is exactly rows*columns.

Complexity

• Time: O(m*n)
• Extra space: O(1) beyond output.

Implementation notes (Go)

• The supplied reference enumerates diagonal sums and chooses direction by parity; it does not use boundary-repair direction toggles.
• Preallocate output capacity m*n with length zero before appending; allocating that length and then appending would add unwanted leading zeros.

Reconstruction checkpoint

What diagonal order comes from [[1,2,3],[4,5,6]]?

Return to Matrix · Module quiz