Where it runs
1. The problem
You have a grid of numbers. You must write all its cells into one flat list, walking the grid along its diagonals. The direction alternates: you read one diagonal from bottom to top and the next one from top to bottom.
For [[1,2,3],[4,5,6],[7,8,9]] the answer is [1,2,4,7,5,3,6,8,9]. The whole task is walking this zig-zag correctly.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedRecognise it
Say these words and it is this pattern
- read or fill a grid in spiral order
- walk a matrix diagonal by diagonal
- rotate a matrix 90 degrees
- visit every cell in a fixed geometric order
Looks similar, isn't
- Matrix search (sorted grid)
That uses the sorted order to skip most of the grid. This one visits every single cell.
- Matrix word search (grid DFS/backtracking)
That searches with backtracking and can turn around. Here the path is fixed in advance.
- Graph BFS / DFS
A traversal follows edges out from a start node. Here the order comes from geometry.
- In-place array transform
Rotating a matrix in place is that idea in two dimensions. The buffer rule is the same.
An r by c grid gives O(rc), because each cell is visited once. Space is O(1) beyond the output.
On LeetCode
Matrix problems that read or group cells along diagonals. Cells on one diagonal share the sum r + c, and on diagonals in the other direction they share the difference r minus c, so either number works as a key.
The main diagonal has r equal to c and the other has r + c equal to n minus 1. Count the centre once when n is odd.
Every cell must equal the one up and to the left, since both sit on the same r minus c diagonal.
The lesson's diagonalOrder. Even diagonals go up, odd ones go down.
Rows have different lengths, so put each cell in a bucket by r + c, starting from the bottom row, and read the buckets in order.
Collect each r minus c diagonal, sort it and write it back into the same cells.