Zigzag Diagonal Readout
MediumMatrix
Problem
An image codec compresses an m × n block by reading it along its anti-diagonals (cells with the same row + column), alternating direction. The diagonal with row + column = 0 is just the top-left cell. Diagonals with an even index are read upwards (from bottom-left to top-right); diagonals with an odd index are read downwards (from top-right to bottom-left).
Return all values in this zigzag order.
Example 1
- Input:
- grid = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
- Output:
- [1, 2, 4, 7, 5, 3, 6, 8, 9]
Diagonals: [1] up, [2, 4] down, [7, 5, 3] up, [6, 8] down, [9] up.
Example 2
- Input:
- grid = [[1, 2], [3, 4]]
- Output:
- [1, 2, 3, 4]
Constraints
- 1 ≤ m, n ≤ 10^4
- 1 ≤ m · n ≤ 10^5
- -10^5 ≤ grid[i][j] ≤ 10^5
Hint
Show the first hint
Every cell on one anti-diagonal shares the same value of r + c. How many anti-diagonals are there?
Walkthrough
How to approach it
01Clarify before coding
- Which direction does the first diagonal go? It is a single cell; the second one (index 1) goes downwards.
- Can the grid be a single row or column? Yes: the output is that row or column in order.
- Do I return values or coordinates? Values.
02Brute force
Bucket every cell into a list keyed by r + c, then reverse every even bucket and concatenate.
Cost: O(m · n) time but O(m · n) extra memory for the buckets on top of the output.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.