LearnWithKiriti

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.
Play
On this page
  1. Revision notes
  2. Brute
  3. Optimal
  4. Variant: Unequal Counts
  5. Follow-up: In Place

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

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.

RearrangeBrute.java
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})));
    }
}
optimal

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.

RearrangeBySign.java
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})));
    }
}
variant

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.

RearrangeUnequal.java
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}));
    }
}
follow-up

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/.

RearrangeInPlace.java
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));
    }
}
RearrangeSwapTrickBreaksOrder.java
// 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));
    }
}