387. Diagonal Traverse
Your function receives an m × n integer matrix mat. Visit every element exactly once in zigzag diagonal order and return the values as a flat array of length m · n.
The order works like this: start at the top-left cell (0, 0). Travel along the anti-diagonal heading up-right; when you run off the matrix, step to the next diagonal and come back down-left; keep alternating until every cell has been visited. All cells on the same anti-diagonal share the same value of row + col, and consecutive diagonals are walked in opposite directions — the first (just the corner cell) counts as an upward one.
Example 1:
Input: mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
Output: [1, 2, 4, 7, 5, 3, 6, 8, 9]
Explanation: Diagonal by diagonal (grouped by row + col): [1], then [2, 4] walked downward, then [7, 5, 3] walked upward, then [6, 8] downward, then [9].
Example 2:
Input: mat = [[1, 2, 3], [4, 5, 6]]
Output: [1, 2, 4, 5, 3, 6]
Explanation: The diagonals are [1], [2, 4] (downward), [5, 3] (upward), and [6]. Note the traversal still alternates even though the matrix is not square.
Constraints:
- 1 ≤ m, n ≤ 100
- m · n ≤ 10⁴
- -10⁵ ≤ mat[i][j] ≤ 10⁵
Hints:
Every cell on the same anti-diagonal has the same value of row + col, and that sum runs from 0 to m + n − 2. What happens if you bucket the cells by that sum?
Filling buckets in row-major order lists each diagonal top-to-bottom. Diagonals with an even index are travelled bottom-to-top, so reverse those buckets before appending. For the O(1)-space version, simulate the walk directly — at each step the edge you hit (right/top or bottom/left) decides the turn, and the order you check the edges in matters at the corners.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
Expected output: [1, 2, 4, 7, 5, 3, 6, 8, 9]