Rearrange Array Elements by Sign
đź’» Try it yourself first. Write your solution in Java, C++, Python or JavaScript and run it against hidden tests, right here.Revision notes
Rearrange Array Elements by Sign (interview style)
Video: “Rearrange Array Elements by Sign” on LearnWithKiriti (Kodee and Mr. Tock). Arrays series, episode 11. LeetCode 2149, Medium.
The array has an even length, equal numbers of positive and negative numbers, and no zeros. Return it so that signs alternate, it starts with a positive, and numbers of the same sign keep their original order. In place is not required.
Example: [3, 1, -2, -5, 2, -4] -> [3, -2, 1, -5, 2, -4]. Smaller: [-1, 2, -3, 4] -> [2, -1, 4, -3].
| Folder | Approach | Time | Extra space |
|---|---|---|---|
Brute/ |
Collect positives and negatives into two lists, then weave them | O(n), two passes | O(n) (two half-lists) |
Optimal/ |
One pass: posIndex = 0 and negIndex = 1, each jumps by two |
O(n), one pass | O(1) (the answer list is not counted) |
FollowUp-InPlace/ |
“Can you do it in place?” Fix each wrong seat by shifting the first matching number into it (keeps order). Also the swap trick, kept only as a warning: it breaks order | O(n^2) | O(1) |
Variant-UnequalCounts/ |
Counts not equal (Alternate Positive Negative on GeeksforGeeks, 0 counts as positive): weave, then append the leftovers | O(n) | O(n) |
Rebuild it
Plus on even, minus on odd. Jump by two. In the answer, positives sit on seats 0, 2, 4… and negatives on seats 1, 3, 5… The brute force puts positives[p] on seat 2p every time, so skip the lists and seat each number directly: keep a “next plus seat” (starts at 0) and a “next minus seat” (starts at 1), and move each one forward by two after using it. Equal counts mean each sign fills its seats exactly.
Order and in place cannot both be cheap. The swap trick is in place and fast but breaks order ([1, 2, 3, -4, -5, -6] gives [1, -5, 3, -4, 2, -6], not [1, -4, 2, -5, 3, -6]); the shift version keeps order but is O(n^2). LeetCode does not require in place, so say so in the interview and give the one-pass answer.
See the pseudocode.md in each folder. Every program was compiled, run and tested (the Python versions were also random-tested against a naive oracle).
Brute
Brute force: two lists, then weave
positives = []
negatives = []
for scan from 0 to size - 1:
if nums[scan] > 0:
positives.add(nums[scan])
else:
negatives.add(nums[scan])
result = new list of size
for pair from 0 to size / 2 - 1:
result[2 * pair] = positives[pair]
result[2 * pair + 1] = negatives[pair]
return result
Dry run on [-1, 2, -3, 4]:
| scan | value | positives | negatives |
|---|---|---|---|
| 0 | -1 | [] | [-1] |
| 1 | 2 | [2] | [-1] |
| 2 | -3 | [2] | [-1, -3] |
| 3 | 4 | [2, 4] | [-1, -3] |
Weave: pair 0 puts 2, -1 on seats 0, 1; pair 1 puts 4, -3 on seats 2, 3. Result [2, -1, 4, -3].
Why it is right: each list is collected left to right, so it keeps its order. Equal sizes mean no pair is missing. Pair p lands on seats 2p and 2p + 1.
Time: O(n), but two passes. Extra space: O(n) (two half-lists, plus the result). It is already linear; the cost is the second pass and the extra lists.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class RearrangeBrute {
static int[] rearrangeBrute(int[] nums) {
int size = nums.length;
List<Integer> positives = new ArrayList<>();
List<Integer> negatives = new ArrayList<>();
for (int scan = 0; scan < size; scan++) {
if (nums[scan] > 0) {
positives.add(nums[scan]);
} else {
negatives.add(nums[scan]);
}
}
int[] result = new int[size];
for (int pair = 0; pair < size / 2; pair++) {
result[2 * pair] = positives.get(pair);
result[2 * pair + 1] = negatives.get(pair);
}
return result;
}
public static void main(String[] args) {
System.out.println(Arrays.toString(rearrangeBrute(new int[]{3, 1, -2, -5, 2, -4})));
System.out.println(Arrays.toString(rearrangeBrute(new int[]{-1, 2, -3, 4})));
System.out.println(Arrays.toString(rearrangeBrute(new int[]{1, 2, 3, -4, -5, -6})));
}
}#include <iostream>
#include <vector>
using namespace std;
vector<int> rearrangeBrute(vector<int>& nums) {
int size = nums.size();
vector<int> positives;
vector<int> negatives;
for (int scan = 0; scan < size; scan++) {
if (nums[scan] > 0) {
positives.push_back(nums[scan]);
} else {
negatives.push_back(nums[scan]);
}
}
vector<int> result(size);
for (int pair = 0; pair < size / 2; pair++) {
result[2 * pair] = positives[pair];
result[2 * pair + 1] = negatives[pair];
}
return result;
}
void printList(const vector<int>& values) {
cout << "[";
for (size_t i = 0; i < values.size(); i++) {
if (i > 0) {
cout << ", ";
}
cout << values[i];
}
cout << "]\n";
}
int main() {
vector<int> nums1 = {3, 1, -2, -5, 2, -4};
printList(rearrangeBrute(nums1));
vector<int> nums2 = {-1, 2, -3, 4};
printList(rearrangeBrute(nums2));
vector<int> nums3 = {1, 2, 3, -4, -5, -6};
printList(rearrangeBrute(nums3));
return 0;
}def rearrange_brute(nums):
size = len(nums)
positives = []
negatives = []
for scan in range(size):
if nums[scan] > 0:
positives.append(nums[scan])
else:
negatives.append(nums[scan])
result = [0] * size
for pair in range(size // 2):
result[2 * pair] = positives[pair]
result[2 * pair + 1] = negatives[pair]
return result
print(rearrange_brute([3, 1, -2, -5, 2, -4]))
print(rearrange_brute([-1, 2, -3, 4]))
print(rearrange_brute([1, 2, 3, -4, -5, -6]))function rearrangeBrute(nums) {
const size = nums.length;
const positives = [];
const negatives = [];
for (let scan = 0; scan < size; scan++) {
if (nums[scan] > 0) {
positives.push(nums[scan]);
} else {
negatives.push(nums[scan]);
}
}
const result = new Array(size);
for (let pair = 0; pair < size / 2; pair++) {
result[2 * pair] = positives[pair];
result[2 * pair + 1] = negatives[pair];
}
return result;
}
const show = (values) => console.log("[" + values.join(", ") + "]");
show(rearrangeBrute([3, 1, -2, -5, 2, -4]));
show(rearrangeBrute([-1, 2, -3, 4]));
show(rearrangeBrute([1, 2, 3, -4, -5, -6]));Optimal
Optimal: one pass, two seat pointers
result = new list of size
posIndex = 0
negIndex = 1
for scan from 0 to size - 1:
if nums[scan] > 0:
result[posIndex] = nums[scan]
posIndex += 2
else:
result[negIndex] = nums[scan]
negIndex += 2
return result
Derivation: in the brute force, positives[p] always lands on seat 2p. So seat each number directly and skip the lists.
Dry run on [-1, 2, -3, 4]:
| scan | value | seat used | posIndex after | negIndex after | result |
|---|---|---|---|---|---|
| 0 | -1 | 1 | 0 | 3 | [_, -1, _, _] |
| 1 | 2 | 0 | 2 | 3 | [2, -1, _, _] |
| 2 | -3 | 3 | 2 | 5 | [2, -1, _, -3] |
| 3 | 4 | 2 | 4 | 5 | [2, -1, 4, -3] |
The main example [3, 1, -2, -5, 2, -4] fills seats 0, 2, 1, 3, 4, 5 in scan order, giving [3, -2, 1, -5, 2, -4].
Seat proof:
- Plus numbers use only even seats and minus numbers only odd seats, so two numbers never land on the same seat.
- There are exactly n/2 plus numbers and exactly n/2 even seats (0, 2, …, n - 2), so every plus number gets a seat and the last one lands on seat n - 2. The same holds for minus numbers and odd seats (the last lands on n - 1). No seat is left empty and nothing runs past the end.
- Scanning left to right hands out each sign’s seats in increasing order, so each sign keeps its original order.
Time: O(n), one pass. Extra space: O(1) besides the output.
import java.util.Arrays;
public class RearrangeBySign {
static int[] rearrangeBySign(int[] nums) {
int size = nums.length;
int[] result = new int[size];
int posIndex = 0;
int negIndex = 1;
for (int scan = 0; scan < size; scan++) {
if (nums[scan] > 0) {
result[posIndex] = nums[scan];
posIndex += 2;
} else {
result[negIndex] = nums[scan];
negIndex += 2;
}
}
return result;
}
public static void main(String[] args) {
System.out.println(Arrays.toString(rearrangeBySign(new int[]{3, 1, -2, -5, 2, -4})));
System.out.println(Arrays.toString(rearrangeBySign(new int[]{-1, 2, -3, 4})));
System.out.println(Arrays.toString(rearrangeBySign(new int[]{1, 2, 3, -4, -5, -6})));
}
}#include <iostream>
#include <vector>
using namespace std;
vector<int> rearrangeBySign(vector<int>& nums) {
int size = nums.size();
vector<int> result(size);
int posIndex = 0;
int negIndex = 1;
for (int scan = 0; scan < size; scan++) {
if (nums[scan] > 0) {
result[posIndex] = nums[scan];
posIndex += 2;
} else {
result[negIndex] = nums[scan];
negIndex += 2;
}
}
return result;
}
void printList(const vector<int>& values) {
cout << "[";
for (size_t i = 0; i < values.size(); i++) {
if (i > 0) {
cout << ", ";
}
cout << values[i];
}
cout << "]\n";
}
int main() {
vector<int> nums1 = {3, 1, -2, -5, 2, -4};
printList(rearrangeBySign(nums1));
vector<int> nums2 = {-1, 2, -3, 4};
printList(rearrangeBySign(nums2));
vector<int> nums3 = {1, 2, 3, -4, -5, -6};
printList(rearrangeBySign(nums3));
return 0;
}def rearrange_by_sign(nums):
size = len(nums)
result = [0] * size
pos_index = 0
neg_index = 1
for scan in range(size):
if nums[scan] > 0:
result[pos_index] = nums[scan]
pos_index += 2
else:
result[neg_index] = nums[scan]
neg_index += 2
return result
print(rearrange_by_sign([3, 1, -2, -5, 2, -4]))
print(rearrange_by_sign([-1, 2, -3, 4]))
print(rearrange_by_sign([1, 2, 3, -4, -5, -6]))function rearrangeBySign(nums) {
const size = nums.length;
const result = new Array(size);
let posIndex = 0;
let negIndex = 1;
for (let scan = 0; scan < size; scan++) {
if (nums[scan] > 0) {
result[posIndex] = nums[scan];
posIndex += 2;
} else {
result[negIndex] = nums[scan];
negIndex += 2;
}
}
return result;
}
const show = (values) => console.log("[" + values.join(", ") + "]");
show(rearrangeBySign([3, 1, -2, -5, 2, -4]));
show(rearrangeBySign([-1, 2, -3, 4]));
show(rearrangeBySign([1, 2, 3, -4, -5, -6]));Variant: Unequal Counts
Variant: unequal counts (Alternate Positive Negative, GeeksforGeeks)
The counts of positive and negative numbers can differ, and 0 counts as positive. Alternate, starting with a positive, while both kinds last; then append the leftovers in their original order.
Why the one-pass seat trick breaks: [3, -1, 5, 7] would put 7 on seat 4 of a size-four array (off the end).
positives = []
negatives = []
for scan from 0 to size - 1:
if nums[scan] >= 0:
positives.add(nums[scan])
else:
negatives.add(nums[scan])
result = []
pair = 0
while pair < positives.size and pair < negatives.size:
result.add(positives[pair])
result.add(negatives[pair])
pair += 1
while pair < positives.size:
result.add(positives[pair])
pair += 1
while pair < negatives.size:
result.add(negatives[pair])
pair += 1
return result
Dry run on [9, 4, -2, -1, 5, 0, -5, -3, 2]: positives [9, 4, 5, 0, 2], negatives [-2, -1, -5, -3]. Weave 4 pairs: [9, -2, 4, -1, 5, -5, 0, -3], then append the leftover 2: [9, -2, 4, -1, 5, -5, 0, -3, 2].
Second example [-5, -2, 5, 2, 4, 7, 1, 8, 0, -8]: positives [5, 2, 4, 7, 1, 8, 0], negatives [-5, -2, -8]. Weave 3 pairs, then append 7, 1, 8, 0: [5, -5, 2, -2, 4, -8, 7, 1, 8, 0].
More: [3, -1, 5, 7] -> [3, -1, 5, 7]; [-4, -2] -> [-4, -2] (only minus numbers, so the weave never runs and the leftovers are the whole list).
Why it is right: both piles keep their order. We alternate until the shorter pile runs out; what is left is all one sign, so it can only be appended in order.
Time: O(n). Extra space: O(n). Zero note: LeetCode 2149 has no zeros; this variant counts 0 as positive.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class RearrangeUnequal {
static List<Integer> rearrangeUnequal(int[] nums) {
List<Integer> positives = new ArrayList<>();
List<Integer> negatives = new ArrayList<>();
for (int scan = 0; scan < nums.length; scan++) {
if (nums[scan] >= 0) {
positives.add(nums[scan]);
} else {
negatives.add(nums[scan]);
}
}
List<Integer> result = new ArrayList<>();
int pair = 0;
while (pair < positives.size() && pair < negatives.size()) {
result.add(positives.get(pair));
result.add(negatives.get(pair));
pair++;
}
while (pair < positives.size()) {
result.add(positives.get(pair));
pair++;
}
while (pair < negatives.size()) {
result.add(negatives.get(pair));
pair++;
}
return result;
}
public static void main(String[] args) {
System.out.println(rearrangeUnequal(new int[]{9, 4, -2, -1, 5, 0, -5, -3, 2}));
System.out.println(rearrangeUnequal(new int[]{-5, -2, 5, 2, 4, 7, 1, 8, 0, -8}));
System.out.println(rearrangeUnequal(new int[]{3, -1, 5, 7}));
System.out.println(rearrangeUnequal(new int[]{-4, -2}));
}
}#include <iostream>
#include <vector>
using namespace std;
vector<int> rearrangeUnequal(vector<int>& nums) {
vector<int> positives;
vector<int> negatives;
for (int scan = 0; scan < nums.size(); scan++) {
if (nums[scan] >= 0) {
positives.push_back(nums[scan]);
} else {
negatives.push_back(nums[scan]);
}
}
vector<int> result;
int pair = 0;
while (pair < positives.size() && pair < negatives.size()) {
result.push_back(positives[pair]);
result.push_back(negatives[pair]);
pair++;
}
while (pair < positives.size()) {
result.push_back(positives[pair]);
pair++;
}
while (pair < negatives.size()) {
result.push_back(negatives[pair]);
pair++;
}
return result;
}
void printList(const vector<int>& values) {
cout << "[";
for (size_t i = 0; i < values.size(); i++) {
if (i > 0) {
cout << ", ";
}
cout << values[i];
}
cout << "]\n";
}
int main() {
vector<int> nums1 = {9, 4, -2, -1, 5, 0, -5, -3, 2};
printList(rearrangeUnequal(nums1));
vector<int> nums2 = {-5, -2, 5, 2, 4, 7, 1, 8, 0, -8};
printList(rearrangeUnequal(nums2));
vector<int> nums3 = {3, -1, 5, 7};
printList(rearrangeUnequal(nums3));
vector<int> nums4 = {-4, -2};
printList(rearrangeUnequal(nums4));
return 0;
}def rearrange_unequal(nums):
positives = []
negatives = []
for scan in range(len(nums)):
if nums[scan] >= 0:
positives.append(nums[scan])
else:
negatives.append(nums[scan])
result = []
pair = 0
while pair < len(positives) and pair < len(negatives):
result.append(positives[pair])
result.append(negatives[pair])
pair += 1
while pair < len(positives):
result.append(positives[pair])
pair += 1
while pair < len(negatives):
result.append(negatives[pair])
pair += 1
return result
print(rearrange_unequal([9, 4, -2, -1, 5, 0, -5, -3, 2]))
print(rearrange_unequal([-5, -2, 5, 2, 4, 7, 1, 8, 0, -8]))
print(rearrange_unequal([3, -1, 5, 7]))
print(rearrange_unequal([-4, -2]))function rearrangeUnequal(nums) {
const positives = [];
const negatives = [];
for (let scan = 0; scan < nums.length; scan++) {
if (nums[scan] >= 0) {
positives.push(nums[scan]);
} else {
negatives.push(nums[scan]);
}
}
const result = [];
let pair = 0;
while (pair < positives.length && pair < negatives.length) {
result.push(positives[pair]);
result.push(negatives[pair]);
pair++;
}
while (pair < positives.length) {
result.push(positives[pair]);
pair++;
}
while (pair < negatives.length) {
result.push(negatives[pair]);
pair++;
}
return result;
}
const show = (values) => console.log("[" + values.join(", ") + "]");
show(rearrangeUnequal([9, 4, -2, -1, 5, 0, -5, -3, 2]));
show(rearrangeUnequal([-5, -2, 5, 2, 4, 7, 1, 8, 0, -8]));
show(rearrangeUnequal([3, -1, 5, 7]));
show(rearrangeUnequal([-4, -2]));Follow-up: In Place
Follow-up: “Can you do it in place?”
Warning first: the swap trick breaks order
evenSeat = 0
oddSeat = 1
while evenSeat < size and oddSeat < size:
if nums[evenSeat] > 0:
evenSeat += 2
else if nums[oddSeat] < 0:
oddSeat += 2
else:
swap(nums[evenSeat], nums[oddSeat])
evenSeat += 2
oddSeat += 2
On the main example it happens to give the right answer, [3, -2, 1, -5, 2, -4]. But on the counter-example [1, 2, 3, -4, -5, -6]:
| step | evenSeat | oddSeat | action | nums |
|---|---|---|---|---|
| 1 | 0 | 1 | 1 is plus, move evenSeat | [1, 2, 3, -4, -5, -6] |
| 2 | 2 | 1 | 3 is plus, move evenSeat | [1, 2, 3, -4, -5, -6] |
| 3 | 4 | 1 | -5 and 2 are both on wrong seats, swap | [1, -5, 3, -4, 2, -6] |
Result [1, -5, 3, -4, 2, -6] (wrong). The answer is [1, -4, 2, -5, 3, -6]. Signs alternate, but a swap makes a number jump over others of its own sign (-5 jumps over -4, 2 jumps over 3), so the order breaks. This is the same reason a swap-based sort is not stable. The files named ...SwapTrickBreaksOrder run this trick only to show the wrong output.
The order-keeping version: shift
for seat from 0 to size - 1:
needsPositive = (seat is even)
if (nums[seat] > 0) == needsPositive:
continue
matchIndex = seat + 1
while (nums[matchIndex] > 0) != needsPositive:
matchIndex += 1
movedValue = nums[matchIndex]
for shiftIndex from matchIndex down to seat + 1:
nums[shiftIndex] = nums[shiftIndex - 1]
nums[seat] = movedValue
Dry run on [1, 2, 3, -4, -5, -6]:
- Seat 0 needs plus, has 1: fine.
- Seat 1 needs minus, has 2: the first minus is at index 3. Shift 2 and 3 right (2 shifts), put -4 on seat 1:
[1, -4, 2, 3, -5, -6]. - Seat 2 needs plus, has 2: fine.
- Seat 3 needs minus, has 3: the first minus is at index 4. Shift 3 right (1 shift), put -5 on seat 3:
[1, -4, 2, -5, 3, -6]. - Seats 4 and 5 are fine. 2 fixes, 3 shifts. Result
[1, -4, 2, -5, 3, -6].
Why it is right: everything between seat and matchIndex has the wrong sign for this seat, and it all shifts right one step without changing its relative order. The moved number was the first of its sign after the seat, so it belongs there. A match always exists because the counts are equal.
Time: O(n^2). The worst case is all plus numbers first, then all minus numbers: m(m - 1)/2 shifts with m = n/2, about n^2/8. Extra space: O(1).
Honest verdict: order and in place cannot both be cheap. LeetCode says in place is not required, so say that in the interview and give the one-pass answer from Optimal/.
import java.util.Arrays;
public class RearrangeInPlace {
static void rearrangeInPlace(int[] nums) {
int size = nums.length;
for (int seat = 0; seat < size; seat++) {
boolean needsPositive = seat % 2 == 0;
boolean isPositive = nums[seat] > 0;
if (needsPositive == isPositive) {
continue;
}
int matchIndex = seat + 1;
while ((nums[matchIndex] > 0) != needsPositive) {
matchIndex++;
}
int movedValue = nums[matchIndex];
for (int shiftIndex = matchIndex; shiftIndex > seat; shiftIndex--) {
nums[shiftIndex] = nums[shiftIndex - 1];
}
nums[seat] = movedValue;
}
}
public static void main(String[] args) {
int[] nums1 = new int[]{3, 1, -2, -5, 2, -4};
rearrangeInPlace(nums1);
System.out.println(Arrays.toString(nums1));
int[] nums2 = new int[]{-1, 2, -3, 4};
rearrangeInPlace(nums2);
System.out.println(Arrays.toString(nums2));
int[] nums3 = new int[]{1, 2, 3, -4, -5, -6};
rearrangeInPlace(nums3);
System.out.println(Arrays.toString(nums3));
}
}// WARNING: the swap trick BREAKS ORDER. Signs alternate, but same-sign numbers can change order. Shown only as a counter-example; the order-keeping shift version (rearrangeInPlace) in this folder is the correct in-place answer.
import java.util.Arrays;
public class RearrangeSwapTrickBreaksOrder {
static void rearrangeSwapTrick(int[] nums) {
int size = nums.length;
int evenSeat = 0;
int oddSeat = 1;
while (evenSeat < size && oddSeat < size) {
if (nums[evenSeat] > 0) {
evenSeat += 2;
} else if (nums[oddSeat] < 0) {
oddSeat += 2;
} else {
int held = nums[evenSeat];
nums[evenSeat] = nums[oddSeat];
nums[oddSeat] = held;
evenSeat += 2;
oddSeat += 2;
}
}
}
public static void main(String[] args) {
int[] nums1 = new int[]{3, 1, -2, -5, 2, -4};
rearrangeSwapTrick(nums1);
System.out.println(Arrays.toString(nums1));
int[] nums2 = new int[]{1, 2, 3, -4, -5, -6};
rearrangeSwapTrick(nums2);
System.out.println(Arrays.toString(nums2));
}
}#include <iostream>
#include <vector>
using namespace std;
void rearrangeInPlace(vector<int>& nums) {
int size = nums.size();
for (int seat = 0; seat < size; seat++) {
bool needsPositive = seat % 2 == 0;
bool isPositive = nums[seat] > 0;
if (needsPositive == isPositive) {
continue;
}
int matchIndex = seat + 1;
while ((nums[matchIndex] > 0) != needsPositive) {
matchIndex++;
}
int movedValue = nums[matchIndex];
for (int shiftIndex = matchIndex; shiftIndex > seat; shiftIndex--) {
nums[shiftIndex] = nums[shiftIndex - 1];
}
nums[seat] = movedValue;
}
}
void printList(const vector<int>& values) {
cout << "[";
for (size_t i = 0; i < values.size(); i++) {
if (i > 0) {
cout << ", ";
}
cout << values[i];
}
cout << "]\n";
}
int main() {
vector<int> nums1 = {3, 1, -2, -5, 2, -4};
rearrangeInPlace(nums1);
printList(nums1);
vector<int> nums2 = {-1, 2, -3, 4};
rearrangeInPlace(nums2);
printList(nums2);
vector<int> nums3 = {1, 2, 3, -4, -5, -6};
rearrangeInPlace(nums3);
printList(nums3);
return 0;
}// WARNING: the swap trick BREAKS ORDER. Signs alternate, but same-sign numbers can change order. Shown only as a counter-example; the order-keeping shift version (rearrangeInPlace) in this folder is the correct in-place answer.
#include <utility>
#include <iostream>
#include <vector>
using namespace std;
void rearrangeSwapTrick(vector<int>& nums) {
int size = nums.size();
int evenSeat = 0;
int oddSeat = 1;
while (evenSeat < size && oddSeat < size) {
if (nums[evenSeat] > 0) {
evenSeat += 2;
} else if (nums[oddSeat] < 0) {
oddSeat += 2;
} else {
swap(nums[evenSeat], nums[oddSeat]);
evenSeat += 2;
oddSeat += 2;
}
}
}
void printList(const vector<int>& values) {
cout << "[";
for (size_t i = 0; i < values.size(); i++) {
if (i > 0) {
cout << ", ";
}
cout << values[i];
}
cout << "]\n";
}
int main() {
vector<int> nums1 = {3, 1, -2, -5, 2, -4};
rearrangeSwapTrick(nums1);
printList(nums1);
vector<int> nums2 = {1, 2, 3, -4, -5, -6};
rearrangeSwapTrick(nums2);
printList(nums2);
return 0;
}def rearrange_in_place(nums):
size = len(nums)
for seat in range(size):
needs_positive = seat % 2 == 0
is_positive = nums[seat] > 0
if needs_positive == is_positive:
continue
match_index = seat + 1
while (nums[match_index] > 0) != needs_positive:
match_index += 1
moved_value = nums[match_index]
for shift_index in range(match_index, seat, -1):
nums[shift_index] = nums[shift_index - 1]
nums[seat] = moved_value
nums1 = [3, 1, -2, -5, 2, -4]
rearrange_in_place(nums1)
print(nums1)
nums2 = [-1, 2, -3, 4]
rearrange_in_place(nums2)
print(nums2)
nums3 = [1, 2, 3, -4, -5, -6]
rearrange_in_place(nums3)
print(nums3)# WARNING: the swap trick BREAKS ORDER. Signs alternate, but same-sign numbers can change order. Shown only as a counter-example; the order-keeping shift version (rearrangeInPlace) in this folder is the correct in-place answer.
def rearrange_swap_trick(nums):
# Pseudocode and trace only (not typed on screen). Signs alternate, but the order can break.
size = len(nums)
even_seat = 0
odd_seat = 1
while even_seat < size and odd_seat < size:
if nums[even_seat] > 0:
even_seat += 2
elif nums[odd_seat] < 0:
odd_seat += 2
else:
nums[even_seat], nums[odd_seat] = nums[odd_seat], nums[even_seat]
even_seat += 2
odd_seat += 2
nums1 = [3, 1, -2, -5, 2, -4]
rearrange_swap_trick(nums1)
print(nums1)
nums2 = [1, 2, 3, -4, -5, -6]
rearrange_swap_trick(nums2)
print(nums2)function rearrangeInPlace(nums) {
const size = nums.length;
for (let seat = 0; seat < size; seat++) {
const needsPositive = seat % 2 === 0;
const isPositive = nums[seat] > 0;
if (needsPositive === isPositive) {
continue;
}
let matchIndex = seat + 1;
while ((nums[matchIndex] > 0) !== needsPositive) {
matchIndex++;
}
const movedValue = nums[matchIndex];
for (let shiftIndex = matchIndex; shiftIndex > seat; shiftIndex--) {
nums[shiftIndex] = nums[shiftIndex - 1];
}
nums[seat] = movedValue;
}
}
const show = (values) => console.log("[" + values.join(", ") + "]");
const nums1 = [3, 1, -2, -5, 2, -4];
rearrangeInPlace(nums1);
show(nums1);
const nums2 = [-1, 2, -3, 4];
rearrangeInPlace(nums2);
show(nums2);
const nums3 = [1, 2, 3, -4, -5, -6];
rearrangeInPlace(nums3);
show(nums3);// WARNING: the swap trick BREAKS ORDER. Signs alternate, but same-sign numbers can change order. Shown only as a counter-example; the order-keeping shift version (rearrangeInPlace) in this folder is the correct in-place answer.
function rearrangeSwapTrick(nums) {
const size = nums.length;
let evenSeat = 0;
let oddSeat = 1;
while (evenSeat < size && oddSeat < size) {
if (nums[evenSeat] > 0) {
evenSeat += 2;
} else if (nums[oddSeat] < 0) {
oddSeat += 2;
} else {
const held = nums[evenSeat];
nums[evenSeat] = nums[oddSeat];
nums[oddSeat] = held;
evenSeat += 2;
oddSeat += 2;
}
}
}
const show = (values) => console.log("[" + values.join(", ") + "]");
const nums1 = [3, 1, -2, -5, 2, -4];
rearrangeSwapTrick(nums1);
show(nums1);
const nums2 = [1, 2, 3, -4, -5, -6];
rearrangeSwapTrick(nums2);
show(nums2);