Reorder Positives and Negatives in Array

Problem Statement

Given an array of positive and negative integers, reorder so that all positives appear before all negatives (or alternating, depending on the variant), while maintaining the relative order within each group.

Variant A (grouped):

Input: nums = [1, -2, 3, -4, 5, -6]
Output: [1, 3, 5, -2, -4, -6]

Variant B (alternating, LC 2149 style — positives first, then alternate):

Input: nums = [3, 1, -2, -5, 2, -4]
Output: [3, -2, 1, -5, 2, -4]
Explanation: Even indices hold positives in original order (3, 1, 2); odd indices hold negatives in original order (-2, -5, -4).

Constraints:

• 1 <= nums.length <= 10^5.
• The array contains equal counts of positive and negative numbers (for Variant B).

Difficulty: Medium LC: 2149 (for the alternating variant) Round: Technical R1

---

Pattern Recognition

• What is the input structure? An array mixing positives and negatives (assume no zeros for Variant B).
• What are we optimizing? Reorder while preserving relative order.
• What pattern does this fit? Partition (two-pass) with extra space, or two-pointer in-place.
• Why does this pattern fit? Stability requires preserving original order. A two-pass solution collects each group and concatenates; in-place stable partition is much harder (O(n log n) or complex rotations).

---

Approach

Brute Force — Sort by Sign

Stable-sort by sign. O(n log n). Works but overkill.

Optimal (Variant A) — Two-Pass Filter

Key Insight: Collect positives in order, then negatives in order. Concatenate.

Step-by-step:

1. Filter positives = [x for x in nums if x >= 0].
2. Filter negatives = [x for x in nums if x < 0].
3. Return positives + negatives.

Time: O(n). Space: O(n).

Optimal (Variant B, LC 2149) — Two Index Pointers into Output

Key Insight: In the output, positives occupy even indices and negatives occupy odd indices (assuming positives come first). Walk the input once and write each positive to out[posIdx], each negative to out[negIdx], advancing by 2.

Step-by-step:

1. out = new array of size n.
2. posIdx = 0, negIdx = 1.
3. For x in nums:
   • If x > 0: out[posIdx] = x, posIdx += 2.
   • Else: out[negIdx] = x, negIdx += 2.
4. Return out.

Time: O(n). Space: O(n) for output.

---

Walkthrough (Variant B)

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

posIdx = 0, negIdx = 1, out = [_, _, _, _, _, _].

x	sign	action	out
3	+	out[0] = 3, posIdx = 2	[3, _, _, _, _, _]
1	+	out[2] = 1, posIdx = 4	[3, _, 1, _, _, _]
-2	-	out[1] = -2, negIdx = 3	[3, -2, 1, _, _, _]
-5	-	out[3] = -5, negIdx = 5	[3, -2, 1, -5, _, _]
2	+	out[4] = 2, posIdx = 6	[3, -2, 1, -5, 2, _]
-4	-	out[5] = -4, negIdx = 7	[3, -2, 1, -5, 2, -4]

Answer: [3, -2, 1, -5, 2, -4].

---

Implementation

TypeScript

// Variant A: group positives before negatives, stable.
function reorderPositivesNegatives(nums: number[]): number[] {
    const positives = nums.filter(x => x >= 0);
    const negatives = nums.filter(x => x < 0);
    return [...positives, ...negatives];
}

// Variant B (LC 2149): alternate starting with positive; preserve relative order within group.
function rearrangeAlternating(nums: number[]): number[] {
    const out: number[] = new Array(nums.length);
    let posIdx = 0, negIdx = 1;
    for (const x of nums) {
        if (x > 0) {
            out[posIdx] = x;
            posIdx += 2;
        } else {
            out[negIdx] = x;
            negIdx += 2;
        }
    }
    return out;
}

C++

#include <vector>

std::vector<int> reorderPositivesNegatives(const std::vector<int>& nums) {
    std::vector<int> out;
    out.reserve(nums.size());
    for (int x : nums) if (x >= 0) out.push_back(x);
    for (int x : nums) if (x < 0) out.push_back(x);
    return out;
}

std::vector<int> rearrangeAlternating(const std::vector<int>& nums) {
    std::vector<int> out(nums.size());
    int posIdx = 0, negIdx = 1;
    for (int x : nums) {
        if (x > 0) { out[posIdx] = x; posIdx += 2; }
        else       { out[negIdx] = x; negIdx += 2; }
    }
    return out;
}

Watch out:

1. Zero handling. Is zero positive, negative, or its own case? Clarify. Variant B typically forbids zeros.
2. Unequal counts. Variant B requires equal counts. If unequal, the interleaved pattern breaks — ask the interviewer.
3. Stable vs unstable partition in-place. A two-pointer swap approach (like Dutch flag) is O(n) but destroys relative order within groups. Clarify stability.

---

Complexity Analysis

	Time	Space
Stable Sort	O(n log n)	O(1) or O(n)
Two-Pass Filter (Variant A)	O(n)	O(n)
Two-Index Write (Variant B)	O(n)	O(n)

Bottleneck: Every element must be visited. Output size = input size, so space is unavoidable unless in-place.

---

Edge Cases

1. All positives — output = input.
2. All negatives — output = input (Variant A); undefined for Variant B.
3. Empty array — output = empty.
4. Alternating input already — unchanged (Variant B).
5. Single element — trivial.
6. Zero present — clarify convention. Typically treat zero as positive (>= 0).

---

Related Problems

• LC 75 — Sort Colors (Dutch National Flag) — Three-color in-place partition (not stable for within-color order).
• LC 283 — Move Zeroes — Stable partition with zero on one side.
• LC 905 — Sort Array By Parity — Same shape, even/odd instead of positive/negative.
• LC 922 — Sort Array By Parity II — Exactly the alternating variant but on parity.

---

Interview Strategy Notes

This is a common Technical R1 warmup or pair-programming problem. 10-15 minutes. The interviewer often follows up with "Now do it in-place with stable order" — this is hard (O(n log n) via merge-sort-like rotations or accept instability). Acknowledge the tradeoff upfront.

---

What is Expected at Each Level

Junior: Two-pass filter. May fumble the alternating variant.

Mid-level: Both variants cleanly. Clarifies stability requirement. Handles zero.

Senior: Discusses in-place stable partition (notes it requires O(n log n) or O(n^2) for true stability). Offers the unstable O(n) in-place with a swap pointer as a fallback and explains the tradeoff.