Rearrange Positives and Negatives Alternately
Solve this ProblemEasy15 min
Topics
BasicsArraysTwo Pointer
Companies
TCSInfosysWipro
Given an array of even length containing equally many positive and negative numbers (and no zeros), return a rearrangement in which positives and negatives alternate, starting with a positive. Within each sign, the values must keep their original order.
Keeping the original order within each group makes this a stableStable RearrangementA reordering that keeps equal-category elements in their original relative order. rearrangement. Because the final position of every value can be worked out in advance, the second solution uses two write pointersWrite PointerAn index that marks where the next value should be written in an output array. that each advance by two, filling the even and odd slots in a single pass.
Test Case 1:
Input:nums = [5, -2, 9, 4, -7, -1]
Output:[5, -2, 9, -7, 4, -1]
Explanation:Positives keep their order (5, 9, 4), negatives keep theirs (−2, −7, −1), and they take turns starting with a positive.
Test Case 2:
Input:nums = [-3, 8]
Output:[8, -3]
Explanation:The positive must come first.
Constraints
- ◆
2 ≤ nums.length ≤ 1000, and the length is even - ◆
exactly half the values are positive and half are negative - ◆
-1000000 ≤ nums[i] ≤ 1000000, nums[i] ≠ 0
Try the Dry Run
Approach & Solutions
Split, Then InterleaveGood
Go through the array once, putting positives into one list and negatives into another; each list keeps the original order. Then build the answer by taking the i-th positive for position 2i and the i-th negative for position 2i + 1.
Time
O(n)Space
O(n)Java
class Solution {
public int[] alternateSigns(int[] nums) {
List<Integer> positives = new ArrayList<>();
List<Integer> negatives = new ArrayList<>();
for (int value : nums) {
if (value > 0) {
positives.add(value);
} else {
negatives.add(value);
}
}
int[] result = new int[nums.length];
for (int i = 0; i < positives.size(); i++) {
result[2 * i] = positives.get(i);
result[2 * i + 1] = negatives.get(i);
}
return result;
}
}Write Straight into Even and Odd SlotsOptimal
The final positions are fixed in advance: positives go to indexes 0, 2, 4, … and negatives to 1, 3, 5, … Keep two write positions, pos = 0 and neg = 1, and walk the input once, placing each value at its sign's next slot and moving that position on by 2. No temporary lists are needed.
Time
O(n)Space
O(n)Java
class Solution {
public int[] alternateSigns(int[] nums) {
int[] result = new int[nums.length];
int pos = 0, neg = 1;
for (int value : nums) {
if (value > 0) {
result[pos] = value;
pos += 2;
} else {
result[neg] = value;
neg += 2;
}
}
return result;
}
}