238. Diagonal Zigzag
A robot vacuum cleans a rectangular floor, and grid[i][j] is the amount of dust on the tile at row i, column j. The robot sweeps the floor along its anti-diagonals: the tiles whose row index plus column index equal the same number d. It starts at the top-left tile (d = 0) and then handles d = 1, d = 2, and so on, up to the bottom-right tile.
The robot alternates its direction. For an even d it walks the diagonal upwards, from its bottom-left end to its top-right end (the row index decreases). For an odd d it walks downwards, from its top-right end to its bottom-left end (the row index increases). Return the dust amounts in the order the robot visits the tiles. The floor can have up to a million tiles, so the sweep must be done in a single linear pass.
Example 1
- Input:
- grid = [[1,2],[3,4]]
- Output:
- [1,2,3,4]
- Explanation:
Diagonal 0 is [1]. Diagonal 1 holds 2 (top-right end) and 3 (bottom-left end) and is walked downwards: 2, 3. Diagonal 2 is [4]. Result: 1, 2, 3, 4.
Example 2
- Input:
- grid = [[2,4,6,8],[1,3,5,7]]
- Output:
- [2,4,1,3,6,8,5,7]
- Explanation:
d = 0: 2. d = 1 (downwards): 4, 1. d = 2 (upwards, bottom-left first): 3, 6. d = 3 (downwards): 8, 5. d = 4: 7.
Example 3
- Input:
- grid = [[9],[8],[7]]
- Output:
- [9,8,7]
- Explanation:
A single column has only one tile per diagonal, so the order is simply 9, 8, 7.
Constraints
1 ≤ grid.length, grid[0].length ≤ 1000
1 ≤ grid.length × grid[0].length ≤ 106
-109 ≤ grid[i][j] ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(m × n)
- Space
- O(m × n)