1508. Every Diagonal on Its Own Line
An R by C grid is given. A DIAGONAL is a set of cells sharing the same value
of column - row, read from its topmost cell downwards and to the right.
There are R + C - 1 diagonals, one for each value of column - row from
-(R - 1) up to C - 1. Print them in that order, one per line.
1 2 3 4 9
5 6 7 8 -> 5 10
9 10 11 12 1 6 11
2 7 12
3 8
4
1 2 3 4 -> 1 a single row: four diagonals of one cell each
2
3
4
1 -> 4 a single column, printed in the opposite order
2 3
3 2
4 1
## What most people try first
Two nested loops over the grid, collecting into buckets keyed by
column - row. That is right, and the reflex that follows it is wrong: keying
a bucket array by column - row DIRECTLY means negative indices, and
buckets[-3] is a crash in C and Java and silently the wrong end of the array
in Python.
The other reflex is to run the diagonal index from 0 to R + C - 2 and start
each at grid[0][d]. That is only valid while d < C. For the first R - 1
diagonals the starting cell is on the left EDGE, not the top row, and a square
grid hides half of the difference.
## Start each diagonal at its own topmost cell
for d in -(R-1) .. C-1:
i = 0 if d >= 0 else -d
j = d if d >= 0 else 0
while i < R and j < C:
emit g[i][j]; i++; j++
A diagonal with d >= 0 starts on the top row at column d. One with d < 0
starts in column 0 at row -d. Shifting the index by R - 1 to get a
non-negative bucket key is the same idea from the other side.
## Why every cell is printed exactly once
Each cell has exactly one value of column - row, so it can never belong to two
diagonals, and it always belongs to one. The walk inside a diagonal moves both
coordinates by one and stops at the first edge, so it visits each cell of that
diagonal exactly once because no cell can be skipped without leaving the grid. The
total printed is therefore exactly R * C.
## The lengths are not symmetric
On a 3 by 4 grid the diagonal lengths are 1 2 3 3 2 1: TWO of them have the
full length 3. On a square grid exactly one does. Code that assumes a unique
longest diagonal, for instance by looking for the one that starts at the top
left, is right on squares and wrong on every rectangle.
## Overflow
Values fit in a signed 32 bit integer, whose limit is 2147483647, and
nothing is combined.
## Cost
O(R C) time and O(R C) for the grid. Problem 1509 groups by
row + column instead, which is the other family of diagonals.
Constraints - `1 ≤ R ≤ 1000` - `1 ≤ C ≤ 1000` - `-10^9 ≤ each value ≤ 10^9` - `R` and `C` are independent; the grid need not be square
Input
The first line contains two integers R and C.
Each of the next R lines contains C integers.
Output
Print R + C - 1 lines, one per diagonal, in increasing order of column - row from -(R - 1) to C - 1. Each line holds that diagonal's values from its topmost cell downwards, separated by single spaces.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.