Rearrange Array Elements by Sign
Rearrange Array Elements by Sign is LeetCode 2149 (Medium). You are given an integer array nums of even length that holds exactly as many positive numbers as negative ones. No element is zero.
Return the array rearranged so that all three conditions hold:
- Signs alternate: every pair of neighbours has opposite signs.
- Order is kept inside each sign: the positives appear in the same order they had in
nums, and so do the negatives. - Positive first: the result starts with a positive number.
The array can hold up to 2 × 10⁵ elements, so the answer should come from a single linear pass rather than repeated shifting.
- 2 <= nums.length <= 2 * 10⁵
- nums.length is even
- 1 <= |nums[i]| <= 10⁵
- nums consists of equal number of positive and negative integers.
Intuition
The three rules fix the answer completely. Positive first plus alternation means every positive sits at an even index and every negative at an odd one. Keeping each sign's order means the k-th positive read from nums must land on the k-th even slot, and the k-th negative on the k-th odd slot.
So nothing has to be searched or swapped. Read nums once and send each number to the next free slot of its own lane. Because the input is read in order and each lane fills in order, stability comes for free, and the equal-count guarantee makes both lanes fill up exactly as the input runs out.
When the final position of each element is decided by a simple rule (its parity, its rank within a group), compute the position and write straight into a result array instead of moving elements around. Here the rule is "k-th positive goes to index 2k, k-th negative to index 2k + 1", which two strided pointers produce without ever computing k.
Approach
Before reading on: write down which index the 3rd positive number must end up at, and which index the 3rd negative must end up at. Then aim for one pass and O(n) time.
Two ways to solve it
Write each number straight into res at pos (even slots) or neg (odd slots), moving that pointer by 2.
- Passes: one over
nums. - Extra memory: only the output array.
- Code: one loop, two counters.
The version to write in an interview.
Collect the positives and the negatives into two lists, then write them back alternately.
- Passes: two, plus the merge.
- Extra memory: two lists of n/2 on top of the output.
- Bonus: extends to unequal counts.
Easiest to see is correct; slightly more work.
Both run in linear time, but the pointer version makes one pass and needs no lists beyond the output. The steps, code and live demo below follow it; the split-and-interleave code comes after the demo.
Allocate the result
Create res with the same length as nums. Writing into a separate array lets each element go straight to its final slot without disturbing anything still unread.
Set the two lane pointers
pos = 0 is the next free even slot and neg = 1 the next free odd slot. Starting pos at 0 is what makes the answer begin with a positive.
Place each element in one pass
- Positive
x:res[pos] = x, thenpos += 2. - Negative
x:res[neg] = x, thenneg += 2.
The step of 2 keeps each pointer inside its own lane and leaves the slot in between for the other sign.
Return res
With n/2 numbers of each sign, every even and every odd slot is written exactly once, so res alternates, starts positive and keeps both orders. It is the only array that does, so it is the answer.
Rearrange Array Elements by Sign solution in Python | C++ | Java
pos = 0, neg = 1.pos points: index 0. Then pos jumps 2 to 2, skipping the odd slot between, which belongs to a negative.pos points: index 2. Then pos jumps 2 to 4, skipping the odd slot between, which belongs to a negative.neg jumps 2 to 3.neg jumps 2 to 5.pos points: index 4. Then pos jumps 2 to 6, skipping the odd slot between, which belongs to a negative.neg jumps 2 to 7. Both pointers have now run off the end together, which is the equal-count guarantee at work.res: P1, N1, P2, N2… Positives appear in the order they had in nums, and so do negatives, because each lane was filled in reading order. No element was ever moved twice.pos = 0, neg = 1.neg jumps 2 to 3.neg runs ahead while pos waits at 0. Order inside the negative lane is unaffected. neg jumps 2 to 5.pos points: index 0. Then pos jumps 2 to 2, skipping the odd slot between, which belongs to a negative.pos points: index 2. Then pos jumps 2 to 4. Both pointers have now run off the end together, which is the equal-count guarantee at work.res: P1, N1, P2, N2… Positives appear in the order they had in nums, and so do negatives, because each lane was filled in reading order. No element was ever moved twice.pos = 0, neg = 1.neg jumps 2 to 3.pos points: index 0. Then pos jumps 2 to 2. Both pointers have now run off the end together, which is the equal-count guarantee at work.res: P1, N1, P2, N2… Positives appear in the order they had in nums, and so do negatives, because each lane was filled in reading order. No element was ever moved twice.Split, then interleave
One pass collects the positives and the negatives in their original order. A second loop writes the i-th positive to index 2i and the i-th negative to index 2i + 1.
Common pitfalls
Swapping in place to fix wrong-sign slots
for i in range(len(nums)):
if wrong_sign(i):
j = next_with_other_sign(i)
nums[i], nums[j] = nums[j], nums[i]res = [0] * len(nums) # write each x to its lane pointer
A swap sends nums[i] to position j, jumping over elements of the same sign and breaking their relative order. Keeping order in place needs a rotation instead of a swap, which is O(n) per fix and O(n²) overall.
Advancing a pointer by 1
res[pos] = x pos += 1
res[pos] = x pos += 2
With a step of 1 the positive pointer walks onto odd slots, and a later negative overwrites a positive already written there. Each lane has to skip the other lane's slot.
Starting the pointers the wrong way round
pos, neg = 1, 0
pos, neg = 0, 1
The output still alternates and keeps both orders, so it looks right, but it starts with a negative. The problem requires a positive at index 0.
Complexity
Rearrange Array Elements by Sign FAQ
Can rearrange array elements by sign LeetCode 2149 be done in place?
Not in linear time while keeping the relative order. A stable in-place rearrangement needs rotations, which cost O(n²) in the simple form. The two-pointer version with a result array is the accepted answer.
What if the numbers of positives and negatives are not equal?
That is the follow-up variant of rearrange array by sign (on GFG, Alternate positive and negative numbers). Split the numbers into a positive list and a negative list, interleave while both have elements, then append whatever is left of the longer list in its original order.