Rearrange Array Elements by Sign
Medium Two write indexes
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
The array has equal numbers of positives and negatives. Rearrange so signs alternate starting with a positive, keeping the original relative order within each sign.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: alternate positive, negative, positive… keeping each group's order.
Why this works: positives always go to even slots and negatives to odd slots, so two write pointers stepping by 2 do the job.
Example: [3, 1, -2, -5, 2, -4]
3 → slot 0, 1 → slot 2, 2 → slot 4-2 → slot 1, -5 → slot 3, -4 → slot 5[3, -2, 1, -5, 2, -4]
✦Hints open one at a time
↗Approach
Make a result array. Scan nums; put each positive at pos (then pos += 2) and each negative at neg (then neg += 2). Order inside each group is preserved automatically.
</>Solution (Java)
class Solution {
public int[] rearrangeArray(int[] nums) {
int[] res = new int[nums.length];
int pos = 0, neg = 1;
for (int x : nums) {
if (x > 0) { res[pos] = x; pos += 2; }
else { res[neg] = x; neg += 2; }
}
return res;
}
}!Common mistake
Trying to swap in place — that breaks the required relative order.
- Time: O(n).
- Space: O(n) for the output.
