You are given a 0-indexed integer array nums of even length. It holds an equal number of positive and negative integers.
Rearrange the values so the result satisfies all three rules:
nums, and likewise for the negatives.Return the rearranged array. You do not need to modify nums in place.
result of the same length.nums from left to right and place positives as you meet them, so their relative order can never change. The same holds for the negatives.Input: nums = [3,1,-2,-5,2,-4] Output: [3,-2,1,-5,2,-4] The positives are [3,1,2] and the negatives are [-2,-5,-4]. Keeping each side's order and starting with a positive gives [3,-2,1,-5,2,-4].
Input: nums = [-1,1] Output: [1,-1] One positive and one negative; starting with the positive gives [1,-1].
- 2 <= nums.length <= 2 * 10^5 - nums.length is even - 1 <= |nums[i]| <= 10^5 - nums has an equal number of positive and negative integers
Rearrange by Sign is a two-way interleave wearing a disguise — the same move that merges two sorted halves in merge sort. The key realization is that you already know each number's destination the instant you read it: positives go to even slots, negatives to odd. That turns a "split then merge" into a single scatter pass.
0, 2, 4, ..., negatives at 1, 3, 5, ... — the interleave, expressed as slots.Given an even-length nums with equal positives and negatives, return an array that alternates signs, starts with a positive, and preserves each sign's original relative order.
Worked example — nums = [3, 1, -2, -5, 2, -4]
even slot (pos): 0 2 4 odd slot (neg): 1 3 5 3→[0] 1→[2] 2→[4] -2→[1] -5→[3] -4→[5] result: [3, -2, 1, -5, 2, -4] ✓
“Are positives and negatives guaranteed equal in count?”
Yes — that's what makes a perfect alternating interleave possible. Unequal counts would need a surplus rule.
“Does the array start with a positive?”
Yes, by the rules — that's what makes the answer unique (otherwise negative-first would also qualify).
“Are zeros possible?”
No — values satisfy |nums[i]| >= 1, so every element is strictly positive or negative.
“Smallest case?”
Length 2, one of each: [-1, 1] becomes [1, -1].
“In place, or a new array?”
A new array is allowed, which is why the clean solutions allocate a fresh result.
“How large can the array be?”
Up to 2×10⁵. Both approaches are O(n); the scatter avoids the two intermediate lists.
A couple of questions.
Equal numbers of positives and negatives, and the result starts with a positive?
Each sign keeps its original relative order?
Then I'll scatter positives to even indices and negatives to odd in one pass.
Because signs must alternate and the array starts positive, the k-th positive lands at index 2k and the k-th negative at index 2k+1. You don't have to decide placement — it's determined by sign and arrival order.
Scan nums once. Place each positive at the next even slot and each negative at the next odd slot. Since you encounter them in original order and never reorder within a sign, relative order is automatically preserved.
The brute force builds a positives list and a negatives list, then merges. But two write pointers — even starting at 0, odd at 1, each stepping by 2 — write directly into the result, skipping the intermediate storage.
| Two lists then interleave | Scatter into slots | |
|---|---|---|
| Idea | Split by sign, then merge alternately | Write each number to its even/odd slot |
| Time | O(n) | O(n) |
| Space | O(n) | O(1) aux |
The full code for both is in the Approaches selector below.
Key takeaway
When an interleave has a fixed pattern, scatter directly to computed slots instead of splitting then merging: positives to even indices, negatives to odd, via two write pointers stepping by 2. One O(n) pass, O(1) auxiliary space, each sign's order preserved for free.