☕ DSA Java Articles

Topics › Arrays › Medium

Rearrange array elements by sign

Medium TUF ID 34 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an array nums of even length that contains exactly as many positive numbers as negative numbers, and no zeros. Rearrange it so that the signs alternate, starting with a positive number: every even index holds a positive value and every odd index holds a negative value. Within the positives, the original relative order must be preserved, and the same holds within the negatives. Return the rearranged array.

Constraints: 2 ≤ n ≤ 2 × 10^5, n is even, nums[i] != 0, values fit in a 32-bit signed integer.

A common follow-up (the second variant on the sheet) drops the “equal counts” promise: alternate for as long as both kinds are available, then append whatever is left over in its original order.

Example 1

nums = [3, 1, -2, -5, 2, -4]
answer = [3, -2, 1, -5, 2, -4]   // positives 3, 1, 2 keep their order; negatives -2, -5, -4 keep theirs

Example 2

nums = [-1, 1]
answer = [1, -1]                 // the positive must come first

Example 3 (unequal counts variant)

nums = [1, 2, -4, -5, 3, 4, 5]
answer = [1, -4, 2, -5, 3, 4, 5] // two pairs, then the three leftover positives in order

Approach 1: Brute force, separate then merge

Intuition. The output is fully determined by two ordered sequences: the positives in order of appearance, and the negatives in order of appearance. If we extract those two sequences, building the answer is just zipping them together, taking one element from each in turn. There is nothing clever here, but it is the natural first solution and it is easy to prove correct: the positives list is in input order, so writing it to indices 0, 2, 4, ... preserves that order, and likewise for the negatives at 1, 3, 5, ....

Algorithm.

  1. Walk the array once; push each positive into pos and each negative into neg.
  2. Allocate the answer array of size n.
  3. For i from 0 to n/2 - 1: write pos[i] to ans[2i] and neg[i] to ans[2i + 1].
  4. Return ans.
static int[] bruteForce(int[] nums) {
    int n = nums.length;
    List<Integer> pos = new ArrayList<>();
    List<Integer> neg = new ArrayList<>();
    for (int x : nums) {
        if (x > 0) pos.add(x); else neg.add(x);
    }
    int[] ans = new int[n];
    for (int i = 0; i < n / 2; i++) {
        ans[2 * i] = pos.get(i);                 // positives go to even indices
        ans[2 * i + 1] = neg.get(i);             // negatives go to odd indices
    }
    return ans;
}

Complexity. Time O(n): one pass to split and one pass of n/2 iterations to merge. Space O(n): the two lists hold all n elements between them, on top of the answer array.

This is already linear, so the “brute force” label is about the extra work and memory, not about asymptotic time. The two intermediate lists are the part worth removing, and the second pass is unnecessary once we notice where each element has to land.

Approach 2: Optimal, one pass with two write pointers

Intuition. The k-th positive (0-indexed) always ends up at index 2k, and the k-th negative always ends up at index 2k + 1, regardless of what else is in the array. So we do not need to collect anything: while reading the input left to right, keep a pointer to the next free even slot and a pointer to the next free odd slot, and write each element straight to its final position. Because we read the input in order, the k-th positive we meet really is the k-th positive, and relative order is preserved automatically.

Why can we not do this in place? Because a positive at index 5 might need to move to index 0 while the element at index 0 has not yet been read. Any in-place scheme has to shift elements around, which costs O(n^2) in the worst case. A separate output array is the price of a single linear pass, and since the problem asks us to return the rearranged array, that output array is not really “extra”.

Algorithm.

  1. Allocate ans of size n; set posIdx = 0 and negIdx = 1.
  2. For each x in nums:
    • If x > 0: ans[posIdx] = x, then posIdx += 2.
    • Otherwise: ans[negIdx] = x, then negIdx += 2.
  3. Return ans.
static int[] optimal(int[] nums) {
    int n = nums.length;
    int[] ans = new int[n];
    int posIdx = 0, negIdx = 1;
    for (int x : nums) {
        if (x > 0) {
            ans[posIdx] = x;
            posIdx += 2;
        } else {
            ans[negIdx] = x;
            negIdx += 2;
        }
    }
    return ans;
}

Dry run on nums = [3, 1, -2, -5, 2, -4]:

x sign written to posIdx after negIdx after ans so far
3 + ans[0] 2 1 [3, _, _, _, _, _]
1 + ans[2] 4 1 [3, _, 1, _, _, _]
-2 - ans[1] 4 3 [3, -2, 1, _, _, _]
-5 - ans[3] 4 5 [3, -2, 1, -5, _, _]
2 + ans[4] 6 5 [3, -2, 1, -5, 2, _]
-4 - ans[5] 6 7 [3, -2, 1, -5, 2, -4]

Complexity. Time O(n): a single pass with constant work per element. Space O(n) for the output array and O(1) beyond it.

The equal-counts guarantee is what makes the write pointers safe: there are exactly n/2 even slots and n/2 odd slots, so neither pointer can run off the end.

Variant: unequal numbers of positives and negatives

Intuition. When the counts differ, the two-pointer trick breaks: the pointer for the more frequent sign would run past n. The required output is “alternate while you can, then dump the rest”, so we go back to the split-then-merge idea. Let k = min(|pos|, |neg|). The first 2k slots are filled by alternating, and the remaining n - 2k slots receive the leftovers of whichever list is longer, in order. Only one of the two leftover loops can actually run, because k equals the size of the shorter list.

Algorithm.

  1. Split into pos and neg as before.
  2. Let k = min(pos.size(), neg.size()). Fill ans[0..2k-1] by alternating.
  3. Append pos[k..] and then neg[k..] starting at index 2k (at most one of these is non-empty).
static int[] unequalCounts(int[] nums) {
    int n = nums.length;
    List<Integer> pos = new ArrayList<>();
    List<Integer> neg = new ArrayList<>();
    for (int x : nums) {
        if (x > 0) pos.add(x); else neg.add(x);
    }
    int[] ans = new int[n];
    int k = Math.min(pos.size(), neg.size());   // number of complete (positive, negative) pairs
    for (int i = 0; i < k; i++) {
        ans[2 * i] = pos.get(i);
        ans[2 * i + 1] = neg.get(i);
    }
    int idx = 2 * k;
    for (int i = k; i < pos.size(); i++) ans[idx++] = pos.get(i);
    for (int i = k; i < neg.size(); i++) ans[idx++] = neg.get(i);
    return ans;
}

Complexity. Time O(n), Space O(n) for the two lists. When the counts happen to be equal this produces exactly the same output as the other two methods, which is what the test harness checks.

Edge cases and pitfalls