Diagonal Traverse
Diagonal Traverse: given an m x n matrix mat, return all elements in diagonal order, alternating between upward and downward diagonals.
- m == mat.length
- n == mat[i].length
- 1 <= m, n <= 10⁴
- 1 <= m * n <= 10⁴
- -10⁵ <= mat[i][j] <= 10⁵
Intuition
Diagonal traverse walks a matrix along its anti-diagonals, alternating direction: the first runs upward, the second downward, and so on.
The organising fact is that every cell on the same anti-diagonal shares one property:
- All cells on a diagonal have the same row + col sum, which ranges from 0 to m + n − 2.
So the traversal is a loop over that sum. For each value, collect every cell whose indices add to it, then reverse the collection on alternate diagonals to produce the zigzag. Diagonals where row + col is even go upward, odd go downward.
That grouped version is the easiest to get right, and its cost is optimal — each cell is visited once.
The alternative simulates the walk directly, moving up-right or down-left and correcting at the boundaries. It saves the intermediate lists but the boundary handling is where it goes wrong. When moving up-right and the row would go negative, the next cell is not simply below: if the column is also at its limit, the move is down instead of right.
Getting that corner wrong is the classic bug, and it only shows on non-square matrices, so square test cases pass while the real input fails.
The grouped approach avoids all of it. Bucket cells by row + col, reverse alternate buckets, and concatenate — no direction state and no boundary cases at all.
When a diagonal traverse matrix problem asks you to walk the diagonals, the key observation is that all cells on the same diagonal share the same value of r + c. Group by that sum, then control the direction with the parity of the diagonal index. This same grouping appears in problems about anti-diagonals and diagonal sorting.
Approach
Before reading on: price up what the direct approach costs here, then ask whether the traversal can carry its state across rows instead of restarting. Aim for O(m * n) time and O(m * n) space.
Group cells by index sum
Every cell on an anti-diagonal shares the same row + col, ranging from 0 to m + n - 2. That single property turns the traversal into a grouping problem.
Collect each diagonal
Bucket every cell by its index sum. Iterating rows and columns naturally fills each bucket in a consistent order, ready to be reversed or kept.
Reverse alternate diagonals
Diagonals with an even sum run upward and odd ones downward. Reversing every other bucket produces the zigzag with no direction variable.
Concatenate for the answer
Joining the buckets in order of increasing sum gives the full traversal. No boundary logic is needed anywhere in this version.
Know the simulation pitfall
Walking directly, when moving up-right and the row goes negative, the next move is down if the column is also at its limit, not right. This corner only fails on non-square matrices, so square tests hide it.
Cost of the traversal
Every cell is visited once, giving O(m · n) time. The grouped version uses O(m · n) space for the buckets; the simulation uses O(1) beyond the output.
Solution & live demo
Common pitfalls
Reversing odd diagonals instead of even ones
if d % 2 == 1:
diags[d].reverse()if d % 2 == 0:
diags[d].reverse()Diagonal 0 goes upward (bottom-to-top), which is even. Row-major scan stores it top-to-bottom, so even diagonals need the reversal. Flipping the parity sends every diagonal the wrong way.
Using r - c instead of r + c for diagonal grouping
d = r - c
d = r + c
r - c groups cells along the other set of diagonals (top-right to bottom-left). The problem asks for anti-diagonals running top-left to bottom-right, which are the r + c lines.
Off-by-one in the number of diagonals
for d in range(m + n):
for d in range(m + n - 1):
The last diagonal index is (m-1) + (n-1) = m + n - 2, so there are m + n - 1 diagonals. Iterating m + n times reads an empty bucket that may not exist, causing an index error.
Edge cases
[[1,2,3]]Each diagonal has exactly one element, so no reversal ever changes anything. The output is the row itself.
[[1],[2],[3]]Same reasoning — each diagonal is length 1. Output is the column read top to bottom.
One diagonal with one element. The loop runs once and returns [mat[0][0]].