Diagonal Traverse

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

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:

• The starting cell lies on either the 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

• Invariant: each element belongs to exactly one diagonal d = r + c.
• Boundary/marker invariants ensure each cell is processed correctly.
• In-place encodings preserve original state until updates are finalized.
• Thus the final matrix matches the required transformation.

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: [2,4] (reversed)
- d=2: [3,5,7] -> traverse as 7,5,3
- d=3: [6,8] (reversed), d=4: [9] -> [1,2,4,7,5,3,6,8,9]

Pitfalls to avoid

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

Complexity

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

Implementation notes (Go)

• Use direction toggles; fix indices when you hit a boundary.
• Pre-allocate the result slice with size m*n.