651. Evens on Even Positions, Odds on Odd
An array is given with exactly as many EVEN values as ODD ones. Rearrange it so that every even POSITION holds an even value and every odd position holds an odd value, counting positions from 0.
Within the evens, and within the odds, the original relative order must be PRESERVED.
4 2 5 7 -> 4 5 2 7
2 3 -> 2 3
1 2 3 4 -> 2 1 4 3
## Two write cursors, not two ends
Problem 626 put all the evens before all the odds. This INTERLEAVES them, and the natural shape is two write cursors rather than two converging ends:
e = 0, o = 1
for each x in the input:
if x is even: out[e] = x; e += 2
else: out[o] = x; o += 2
One read pointer walks the input once; the two write cursors each advance by 2, so they never collide and between them they cover every position exactly once.
## Why stability comes free
Each cursor writes in the order it receives values, so the evens appear at even positions in their original order and likewise for the odds. No extra work is needed, unlike problem 626 where the in-place swap destroys exactly this.
## The in-place version, and what it costs
There is an O(1) memory version: walk e to the first even position holding an ODD value,
walk o to the first odd position holding an EVEN value, and swap them. It is correct, it uses
no extra array, and like 626's swap it does NOT preserve order.
The statement asks for order to be kept, so the two-cursor version with one extra array is the answer. Naming that trade is the point.
## Negative and zero values
In C, C++, Java and JavaScript, -3 % 2 is -1, not 1, so a test for x % 2 == 1 misses
every negative odd number. Compare against 0: x % 2 == 0 is even, anything else is odd.
Zero is even, and the test with zeros is there to confirm it.
## Cost
Time O(n). Space O(n).
Constraints - `2 ≤ n ≤ 200000` and `n` is even - `-10^9 ≤ each value ≤ 10^9` - exactly `n/2` values are even
Input
The first line contains an even integer n.
The second line contains n integers, exactly half of them even.
Output
Print the n rearranged 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.