1513. Sort Every Diagonal

An R by C grid is given. Sort each down-right diagonal into non-decreasing order, from its topmost cell to its bottom one, leaving every value on the diagonal it started on. Print the result.

Cells are on the same diagonal when column - row is equal.

3 3 1 1 -> 1 1 1 1 2 2 1 2 1 2 2 2 1 1 1 2 1 2 3 3

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

9 1 -> 1 1 1 1 1 9

## What most people try first

Sorting each ROW, or sorting the whole grid and refilling it. Both produce a sorted-looking answer and both move values between diagonals, which the statement forbids. The 2 by 2 example is the smallest case where they differ from the right answer: sorting the grid gives 1 1 / 1 9 by coincidence, and sorting the rows gives 1 9 / 1 1, which is wrong.

The second reflex is to sort "the diagonals from the top row", meaning C diagonals starting at g[0][j]. That misses the R - 1 diagonals starting down the left edge entirely. On a square grid those are n - 1 of the 2n - 1, so the bug is visible; on a 1 by 5 grid it is invisible, which is exactly why a rectangle test is needed at both extremes.

## Collect, sort, write back

for each starting cell (i0, j0) on the top row or the left edge: walk down-right collecting values into a list sort the list walk down-right again writing the list back in order

The starting cells are (0, j) for every j, and (i, 0) for every i >= 1. That is R + C - 1 diagonals, each visited twice.

## Why the diagonals partition the grid

Every cell has one value of column - row, and stepping down and right always keeps it fixed while stepping in any other direction always changes it, so no cell can lie on two diagonals. So the diagonals are disjoint and cover the grid, which is what makes sorting them independently well defined at all. It is also why the total sorting work is bounded: the lengths add to R * C.

## The cost of sorting them separately

Sorting a list of length L costs O(L log L), and the lengths add to R * C, so the total is at most O(R C log min(R, C)), since no diagonal is longer than min(R, C). At R = C = 1000 that is about 10^7 comparisons, which is comfortable. Sorting the whole grid instead would be O(R C log(R C)), slightly worse AND wrong.

## Overflow

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

## Cost

O(R C log min(R, C)) time and O(min(R, C)) extra for the one diagonal being sorted. Problem 1512 moves the same diagonals without reordering them, and needs no sorting at all.

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