639. Duplicating Every Zero In Place
Every zero in the array is to be written TWICE, pushing everything after it one place to the right. The array keeps its original LENGTH, so whatever is pushed past the end is lost.
Print the resulting array.
1 0 2 3 0 4 5 0 -> 1 0 0 2 3 0 0 4
1 2 3 -> 1 2 3 nothing changes
0 1 -> 0 0
## Why writing forwards destroys the data
The obvious loop finds a zero and shifts the rest of the array right by one. Each shift is
O(n), so the whole thing is O(n^2), and worse, writing forwards overwrites values that have
not been read yet.
The fix is the one that works for every in-place expansion: write BACKWARDS, from the end, so the cell being written is always past everything still to be read.
## Two passes
First count the zeros. That tells you where each value would land if the array were long
enough: a value at position i moves to i + (zeros before it).
Then walk a read pointer i backwards from the last position and a write pointer j backwards
from n + zeros - 1, which is the last position of the imaginary longer array:
while i >= 0:
if j < n: a[j] = a[i]
j -= 1
if a[i] == 0:
if j < n: a[j] = 0
j -= 1
i -= 1
## The guard that does the truncation
j starts beyond the end of the array, so the early writes fall off and must be skipped. The
if j < n test is exactly that truncation: values that would land past the end are computed
and discarded rather than written.
Dropping the guard writes out of bounds. Starting j at n - 1 instead silently produces the
wrong answer, because the shift distance is then wrong for everything.
## Why the write pointer never overtakes the read pointer
j starts at or after i and falls by 1 or 2 per round while i falls by exactly 1. It can
therefore catch up but never pass, and when it is equal the value written is the value just
read. So no unread value is ever overwritten.
That is the same invariant as problem 622, in the opposite direction.
## Boundaries
An array of all zeros comes back as all zeros: each one is duplicated and each duplicate pushes the rest off the end.
An array with no zeros is unchanged.
## Cost
Time O(n). Space O(1).
Constraints - `1 ≤ n ≤ 200000` - `0 ≤ each value ≤ 10^9`
Input
The first line contains an integer n.
The second line contains n non-negative integers.
Output
Print the n resulting values on one line, separated by single spaces.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.