1528. Push the Zeros to the End of Each Row
An R by C grid is given. In each row independently, move every zero to the
end while keeping the non-zero values in their original left-to-right order.
Print the result.
The work must be done inside the grid: apart from a constant number of scalar variables, no extra storage is allowed.
0 1 0 2 -> 1 2 0 0
3 0 0 4 3 4 0 0
0 0 0 0 0 0 0 0
1 2 3 -> 1 2 3 no zero anywhere, so nothing moves
4 5 6 4 5 6
0 0 1 0 2 0 -> 1 2 0 0 0 0
## What most people try first
Building a new row from the non-zero values and padding it with zeros. Correct,
and it is C extra cells.
The in-place attempt that fails swaps a zero with the value after it, repeatedly.
On 0 0 1 0 2 0 that moves the first zero past the second zero and back again,
and the ORDER of the non-zero values survives only by accident. It is also
O(C^2) per row in the worst case.
## A write pointer trailing a read pointer
for each row:
w = 0
for j in 0 .. C-1:
if g[row][j] != 0:
swap g[row][w] and g[row][j]
w++
When the loop ends, w is the number of non-zero values and positions
w .. C-1 hold the zeros.
## Why the order is preserved
w never exceeds j, so the cell being written to is at or behind the cell
being read. The non-zero values are therefore written in exactly the order they
are met, which is their original order. The swap, rather than a plain
assignment, is what carries the displaced zero forward to position j, so no
value is lost and no zero has to be counted and re-added afterwards.
## Why w == j is not a special case
When no zero has been seen yet, w equals j and the swap exchanges a cell
with itself. That is harmless and costs one pointless write; guarding it with
if w != j is a valid optimisation and not a correctness fix. The row
1 2 3 is the case where every iteration hits it.
## The two degenerate shapes
A single column means every row has exactly one value, so nothing ever moves, whatever that value is. A single row is one pass of the loop. Both fall out of the same code, and the single-column test is the quickest way to catch an implementation that walks COLUMNS by mistake.
## Overflow
Nothing is combined. Values fit in a signed 32 bit integer, whose limit is
2147483647. Note that negative values are ordinary data here: only exact
zeros move.
## Cost
O(R C) time, one pass, and O(1) extra memory.
Constraints - `1 ≤ R ≤ 1000` - `1 ≤ C ≤ 1000` - `-10^9 ≤ each value ≤ 10^9` - only exact zeros move; negative values are ordinary data - no extra array; `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.
Output
Print the rewritten grid as R lines of C integers each, separated by single spaces. In every row the non-zero values come first in their original order, followed by all the zeros.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.