Diagonal Traverse
Given an m x n matrix mat, return all elements in diagonal order, alternating between upward and downward diagonals.
Intuition
Every cell (r, c) belongs to diagonal number r + c. Diagonal 0 is the top-left corner, diagonal 1 holds (0,1) and (1,0), and so on up to diagonal m + n − 2. The twist is direction: even-numbered diagonals travel upward (decreasing row), odd ones travel downward (increasing row). Once you see that r + c groups cells into diagonals, the rest is bookkeeping — collect each diagonal's cells in row order, reverse the even ones, and concatenate.
When a problem asks you to traverse a matrix along its 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
Group cells by their diagonal index `r + c`
Walk the matrix in ordinary row-major order. For each cell (r, c), its diagonal number is d = r + c. Append the value to a bucket for diagonal d. Because we iterate row by row, cells within each bucket are already sorted by increasing row. There are m + n - 1 diagonals in total.
Reverse even-numbered diagonals to alternate direction
Even diagonals (d % 2 == 0) should read bottom-to-top (decreasing row), but our row-major scan stored them top-to-bottom. Reverse those buckets in place. Odd diagonals already read in the correct top-to-bottom direction, so leave them alone.
Flatten the buckets into the result list
Iterate through diagonals 0 to m + n - 2 and extend the result with each bucket. The final list has exactly m n elements. Time is O(m n) for the scan plus the reversal work, which is also bounded by O(m n) in total. Space is O(m n) for the buckets and result.
Solution
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]].