626. Evens Before Odds, Order Kept
Rearrange the values so that every EVEN value comes before every ODD one. Within the evens, and within the odds, the original relative order must be PRESERVED.
3 1 2 4 -> 2 4 3 1
4 1 2 3 5 6 -> 4 2 6 1 3 5
1 3 5 -> 1 3 5 nothing to move
## The classic in-place swap is NOT stable
The usual answer to "evens before odds" converges two pointers and swaps:
i = 0, j = n-1
while i < j:
while i < j and a[i] is even: i += 1
while i < j and a[j] is odd: j -= 1
swap a[i], a[j]
That partitions correctly, uses O(1) memory, and SCRAMBLES the order within each group,
because it moves values across the whole array in one jump.
On 3 1 2 4 it gives 4 2 1 3, while the order-preserving answer is 2 4 3 1. On 300 random
arrays the two disagree on 161 of them, so this is not an edge case; it is the normal
behaviour.
Stability is exactly why the statement asks for the order to be kept. Interviewers ask this version specifically because the fast in-place answer fails it.
## The stable answer: two write passes
w = 0
for each x in a: if x is even, out[w++] = x
for each x in a: if x is odd, out[w++] = x
Each pass is a read pointer and a write pointer moving forward, and each keeps the values it
copies in the order it met them. Two passes, O(n) time, one extra array.
## The trade you are being asked to see
· in-place swap: O(1) memory, order destroyed
· two write passes: O(n) memory, order kept
There is no way to have both in O(n) time with a simple loop. Stable in-place partitioning is
possible, but it costs either O(n log n) time or a much more intricate algorithm, and neither
is what this question is for.
Saying which trade you are making, out loud, is the answer an interviewer is listening for.
## Negative and zero values
Use a test that works for negatives. In C, C++, Java and JavaScript, -3 % 2 is -1, not
1, so x % 2 == 1 misses every negative odd number. Compare against 0 instead:
x % 2 == 0 for even, and anything else for odd.
Zero is even.
## Cost
Time O(n). Space O(n).
Constraints - `1 ≤ n ≤ 200000` - `-10^9 ≤ each value ≤ 10^9`
Input
The first line contains an integer n.
The second line contains n integers.
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.