1510. Zigzag Down the Diagonals

An R by C grid is given. Print every value on one line, anti-diagonal by anti-diagonal, where an anti-diagonal is the set of cells with the same row + column.

Anti-diagonal 0 comes first, then 1, and so on to R + C - 2. The direction ALTERNATES: an even-numbered anti-diagonal is read from its lowest cell upwards and to the right, an odd-numbered one from its highest cell downwards and to the left.

1 2 3 -> 1 2 4 7 5 3 6 8 9 4 5 6 7 8 9

1 2 3 4 -> 1 2 5 6 3 4 7 8 5 6 7 8

1 2 3 4 5 -> 1 2 3 4 5 a single row: every anti-diagonal has one cell

## What most people try first

Collecting each anti-diagonal into a list and reversing every other one. That is correct and it allocates R + C - 1 lists for an answer that is a single sequence. It is worth knowing because it is the easy way to check a walking version against itself, which is exactly what the oracle for this problem does.

The walking version is where the bug lives. The reflex is to start each anti-diagonal at grid[s][0] when going up and at grid[0][s] when going down. Both are outside the grid as soon as s passes an edge, and WHICH edge it passes first depends on the shape. On a wide grid the down-left walks clamp against the last column long before the up-right walks clamp against the last row.

## Clamp the start of each walk

for s in 0 .. R+C-2: if s is even: going up and right i = min(s, R-1); j = s - i while i >= 0 and j < C: emit g[i][j]; i--; j++ else: going down and left j = min(s, C-1); i = s - j while j >= 0 and i < R: emit g[i][j]; i++; j--

## Why the clamp is exactly min against the far index

On anti-diagonal s the lowest cell is the one with the largest row, and rows stop at R - 1, so the starting row for an upward walk is min(s, R - 1). Its column is then forced, because the two must add to s. The downward walk is the same argument with the roles of row and column exchanged. Both expressions are correct for every R and C, including the degenerate ones, because the clamp is what handles the edge rather than a branch.

## The shape that catches a wrong clamp

A 4 by 2 grid has six anti-diagonals and clamps against the last column from s = 2 onwards, while a 2 by 4 grid clamps against the last row from the same point. Swapping the two clamps passes on a square grid, where they coincide, and fails on both of these.

## Overflow

Nothing is combined and values fit in a signed 32 bit integer, whose limit is 2147483647.

## Cost

O(R C) time, since each cell is emitted once, and O(R C) for the grid. Problem 1509 groups the same anti-diagonals but only needs their totals, so it never has to know which end of one it is standing at.

Constraints - `1 ≤ R ≤ 1000` - `1 ≤ C ≤ 1000` - `-10^9 ≤ each value ≤ 10^9` - `R` and `C` are independent; the grid need not be square