Rearrange Array Elements by Sign
Given an array with equal counts of positive and negative numbers, rearrange it so signs alternate starting with a positive, preserving relative order within each sign.
Open on LeetCode ↗Intuition
The instinct is to swap elements into place, and swapping is exactly what breaks this problem: the moment you exchange two entries you scramble the relative order the question asks you to preserve. You never needed to swap. The counts are equal and the pattern is fixed, so every element's destination is already decided before you start — the k-th positive belongs at index 2k, the k-th negative at 2k + 1. Read the input in order and write straight into the answer with two cursors stepping by two.
Approach
Note what the equal-count guarantee buys
With exactly n/2 of each sign and a fixed alternating pattern, the destination of the k-th positive is index 2k and the k-th negative is index 2k + 1. No searching or swapping is needed — the layout is fully determined before you start.
Two write cursors
Keep pos = 0 and neg = 1. Scan the input once; a positive value goes to res[pos] and pos += 2, a negative goes to res[neg] and neg += 2. Reading the input in order is what preserves relative order within each sign, which the problem requires.
Why not swap in place
An in-place version cannot keep relative order without O(n) extra shifting, so it is not actually better. Building a fresh result array is O(n) time and O(n) space and is both simpler and faster. The two-list approach costs the same space but adds an extra pass — the two-cursor version does everything in one.
Solution & live demo
Edge cases
One positive and one negative, so the answer is [pos, neg].
The cursors reproduce it unchanged.
Handled naturally, since the write positions do not depend on input order.
Outside this problem's guarantee — the follow-up variant requires appending the leftovers after the alternation runs out.