1530. Sort the Flattened Grid of Three Colours
An R by C grid is given in which every value is 0, 1 or 2. Sort the
whole grid into non-decreasing order in READING ORDER, left to right within a
row and then on to the next row, and print it.
Sorting is across the whole grid, not per row: a run of a colour crosses a row boundary freely. The work must happen inside the grid, in a SINGLE pass over it, with no extra storage beyond a constant number of scalar variables.
2 0 1 2 -> 0 0 0 0
1 0 0 2 1 1 1 1
1 2 0 1 2 2 2 2
2 1 0 2 1 0 1 -> 0 0 1 1 1 2 2
0 1 2 -> 0 0 0
0 1 2 0 1 1
0 1 2 1 2 2
0 1 2 2 2 2
## What most people try first
Counting how many of each colour there are, then rewriting the grid. That is correct, it needs three counters, and it makes TWO passes over the data. It is the right answer if two passes are allowed, and this problem asks for one, which is the version worth knowing because it also works on a stream that can only be read once.
The other reflex is a general sort. It is O(R C log(R C)) where O(R C) is
available, and it throws away the fact that there are only three values.
## Three regions and three pointers
Read the grid flat. Keep
lo everything before it is 0
mid the cell being examined
hi everything after it is 2
lo = 0; mid = 0; hi = n - 1
while mid <= hi:
if a[mid] == 0: swap a[lo], a[mid]; lo++; mid++
elif a[mid] == 1: mid++
else: swap a[mid], a[hi]; hi--
## Why mid does not advance on a 2
The value arriving from hi has never been examined: it could be any of the
three colours, so it must be looked at next. Advancing mid there is the
single most common bug, and it only shows when the swapped-in value is a 0,
because a 1 or a 2 would be left in an acceptable place by luck. The grid
2 0 / 0 2 is the smallest case that catches it.
By contrast, the value arriving from lo when a 0 is swapped in is always a 1
or the same cell, because lo never runs ahead of mid and everything between
them is a 1. So mid can safely advance there.
## Why the loop ends at mid > hi
Everything after hi is known to be 2 and everything before lo is known to
be 0, so once mid passes hi nothing unexamined remains. Writing
while mid < hi leaves the final cell unexamined; on 2 0 / 0 2 that is
visible in the answer.
## Why sorting the flat array is the same as sorting the grid
Row-major storage means reading order IS increasing flat index, so a sorted
flat array printed C values per line is exactly the sorted grid. No row
boundary needs any special handling, which is why the 4 by 3 example above has
runs that straddle rows.
## Overflow
The values are 0, 1 and 2. Nothing is combined and nothing approaches the
2147483647 a signed 32 bit integer holds.
## Cost
O(R C) time in one pass and O(1) extra memory.
Constraints - `1 ≤ R ≤ 1000` - `1 ≤ C ≤ 1000` - every value is `0`, `1` or `2` - one pass over the grid; `O(1)` extra memory beyond the input - `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, each 0, 1 or 2.
Output
Print the sorted grid as R lines of C integers each, separated by single spaces: all the zeros first, then all the ones, then all the twos, in reading order across the whole grid.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.