Diagonal Traverse
Medium · Matrix · Array · Matrix · Simulation
Problem
You are given an m x n matrix mat. Visit its anti-diagonals (the groups of cells with the same row + col) starting from the top-left corner, alternating direction: the first anti-diagonal is read moving up-right, the next moving down-left, the next up-right again, and so on.
Return every element of mat as a single list in that zigzag order.
Examples
Input: mat = [[1,2,3],[4,5,6]] Output: [1,2,4,5,3,6]
The anti-diagonals are [1], [2,4] read down-left, [5,3] read up-right, and [6].
Input: mat = [[7,8],[9,10],[11,12]] Output: [7,8,9,11,10,12]
Reading 7, then 8 down to 9, then 11 up to 10, then 12.
Input: mat = [[1,2,3],[4,5,6],[7,8,9]] Output: [1,2,4,7,5,3,6,8,9]
The middle anti-diagonal 7, 5, 3 is read upward because it is the third (even-numbered) one.
Constraints
- m == len(mat), n == len(mat[i])
- 1 <= m, n <= 10^4
- 1 <= m · n <= 10^4
- -10^5 <= mat[i][j] <= 10^5
Approaches
- Collect each anti-diagonal by scanning the matrix — time O((m + n) · m · n), space O(min(m, n)) beyond the output
Follow-up
What if you had to return the k-th element of the zigzag order without building the list? Count the cells on each anti-diagonal (they grow by one up to min(m, n), stay flat, then shrink) to find which anti-diagonal holds position k, then compute the cell inside it from the direction of that anti-diagonal: O(m + n) time and O(1) space.
Related problems
Start free on Cariara · Coding problems · System design studio
