Diagonal Traverse
Understanding the Problem
Draw diagonal lines through the matrix, each running from its top-right end to its bottom-left end. The traversal does not read every diagonal in the same direction. The first diagonal goes upward (from bottom-left to top-right), the second goes downward (from top-right to bottom-left), and the direction keeps alternating in a zigzag.
The work in this problem is in the mechanics of that zigzag. Which elements belong to the same diagonal? When does the direction switch? And what happens at the boundaries when a diagonal reaches the edge of the matrix?
All elements on the same diagonal share the same sum of their row and column indices. For example, (0,1) and (1,0) both have row + col = 1, so they belong to the same diagonal. Both approaches below build on this property.
Key Constraints:
1 <= m, n <= 10^4→ The matrix dimensions can be large, but the total number of elements is capped.1 <= m * n <= 10^4→ At most 10,000 elements total. Even O(m n log(m n)) would be fine, but O(m n) is ideal.-10^5 <= mat[i][j] <= 10^5→ Values can be negative, but they are only copied to the output, so no special handling is needed.
Approach 1: Group by Diagonal and Reverse
Intuition
Group elements by the diagonal they belong to. Every element on the same diagonal has the same row + col value, so that sum works as a bucket index. Walk through the matrix in row-major order, append each element to the bucket at index row + col, then read the buckets back out in the correct direction.
Even-indexed diagonals (0, 2, 4, ...) are output bottom-left to top-right; odd-indexed diagonals (1, 3, 5, ...) are output top-right to bottom-left. Row-major iteration fills each bucket in increasing row order, which along a diagonal means decreasing column, the same as top-right to bottom-left. Odd buckets can be emitted as-is; even buckets need a reverse.
Algorithm
- Create a list of lists, one entry per diagonal index from 0 to
m + n - 2. - Iterate through the matrix in row-major order. For each element at
(r, c), append it to the list at indexr + c. - For each diagonal: if the diagonal index is even, reverse the list (to get the upward direction). If odd, leave it as-is.
- Concatenate all the diagonal lists into the result array.
Visualization and Code
Loading animation...
- Time Complexity: O(m * n). We visit every element exactly once during the grouping pass. The concatenation pass also touches every element exactly once.
- Space Complexity: O(m * n). We store all elements in the diagonal buckets before building the result.
This approach stores every element in a bucket before producing any output. The next approach removes the buckets by walking the matrix in diagonal order directly and writing each element to the result as it is visited.
Approach 2: Direct Simulation (Optimal)
Intuition
Instead of grouping and rearranging, walk the matrix in the order the problem describes. Start at (0, 0) and move diagonally up-right (row decreases, column increases). On hitting a boundary, move to the start of the next diagonal and switch direction.
The boundary handling carries the only subtlety. When moving up-right, check the right edge before the top edge. When moving down-left, check the bottom edge before the left edge.
The order of the boundary checks decides the corners, where both conditions are true at once. At the top-right corner (row = 0, col = n - 1) while moving up-right, the correct move is down one row (the right-edge rule); moving right (the top-edge rule) would step out of bounds. Checking the right edge first selects the correct rule. The bottom-left corner (row = m - 1, col = 0) is the symmetric case while moving down-left: the bottom-edge rule (move right) must apply before the left-edge rule (move down), which would also leave the matrix.
Algorithm
- Start at position
(row, col) = (0, 0)with direction going up-right. - For each step, add
mat[row][col]to the result. - Determine the next position based on the current direction and boundary:
- Going up-right: if at right edge (
col == n-1), move down and flip. Else if at top edge (row == 0), move right and flip. Otherwise, normal diagonal step. - Going down-left: if at bottom edge (
row == m-1), move right and flip. Else if at left edge (col == 0), move down and flip. Otherwise, normal diagonal step. - Repeat until all m * n elements are collected.
Visualization and Code
Loading animation...
- Time Complexity: O(m * n). We visit each element exactly once, doing O(1) work per element. The boundary checks are constant-time operations.
- Space Complexity: O(1) extra space. Apart from the output array, we only use a handful of integer variables:
row,col,direction, and the loop counter.