DSA problem
Diagonal Traverse
Given an m x n matrix mat, return an array of all the elements of the array in a diagonal order. The traversal moves along anti-diagonals (cells where the sum of the row and column index is constant), alternating direction: the first diagonal is traversed upward to the right, the next downward to the left, and so on in a zig-zag pattern.
The key observation is that all cells on the same anti-diagonal share the same value of row + col. There are m + n - 1 such diagonals in total, indexed from 0 to m + n - 2. On even-indexed diagonals the traversal goes up-right (decreasing row, increasing column), and on odd-indexed diagonals it goes down-left (increasing row, decreasing column).
The intuition for the optimal approach is a direct simulation that walks one cell at a time, maintaining a current position and a direction. When the path steps outside the matrix, you clamp back inside by choosing the correct entry point of the next diagonal and flip the direction. This visits each cell exactly once with only constant extra space beyond the output, giving linear time in the number of cells.
Examples
mat = [[1,2,3],[4,5,6],[7,8,9]][1,2,4,7,5,3,6,8,9]mat = [[1,2],[3,4]][1,2,3,4]mat = [[1,2,3,4]][1,2,3,4]Constraints
- m == mat.length
- n == mat[i].length
- 1 <= m, n <= 10000
- 1 <= m * n <= 100000
- -100000 <= mat[i][j] <= 100000
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.