Rearrange Positive and Negative Numbers in an Array

Rearranging an array’s positive and negative numbers is three different problems in disguise: all negatives first with no order constraint, all negatives first with relative order preserved, and positives and negatives placed in alternating positions.

Three Variants of the Problem

Most placement question banks list this as a single problem. It isn’t. The three variants share the same input but require different algorithms and carry different complexity trade-offs.

• Variant A — Negatives before positives, order not required: fastest solution, O(n) time, O(1) space.
• Variant B — Negatives before positives, relative order preserved: needs O(n) extra space for an O(n) solution (or O(n^2) time for in-place).
• Variant C — Alternating negatives and positives: needs O(n) space; the split between counts doesn’t have to be equal.

Interviewers often don’t state the variant explicitly in the first 30 seconds. Ask before writing a single line.

Approach 1: Partition In-Place

This is the Lomuto-style partition. A boundary pointer j tracks where the next negative should go. A scan pointer i walks the array left to right. Every time i lands on a negative, swap arr[i] with arr[j] and advance j.

Step-by-step trace

Input: [1, -1, 2, -2, 3, -3]

• j=0, i=0: arr[0] = 1 (positive), no swap. j stays at 0.
• j=0, i=1: arr[1] = -1 (negative), swap arr[1] and arr[0]. Array: [-1, 1, 2, -2, 3, -3]. j = 1.
• j=1, i=2: arr[2] = 2 (positive), no swap. j stays at 1.
• j=1, i=3: arr[3] = -2 (negative), swap arr[3] and arr[1]. Array: [-1, -2, 2, 1, 3, -3]. j = 2.
• j=2, i=4: arr[4] = 3 (positive), no swap. j stays at 2.
• j=2, i=5: arr[5] = -3 (negative), swap arr[5] and arr[2]. Array: [-1, -2, -3, 1, 3, 2]. j = 3.
• Output: [-1, -2, -3, 1, 3, 2]

Negatives (-1, -2, -3) happen to keep their relative order here because they were encountered left to right. Positives (1, 3, 2) do not: 2 and 3 swapped. This is not guaranteed in all cases; the partition is unstable.

The C++ standard library function std::partition implements the same idea. Passing a lambda [](int x){ return x < 0; } gives the same unstable split in one line.

C++ implementation

#include <iostream>
#include <vector>
using namespace std;

void rearrangePartition(vector<int>& arr) {
    int j = 0;
    for (int i = 0; i < (int)arr.size(); i++) {
        if (arr[i] < 0) {
            swap(arr[i], arr[j]);
            j++;
        }
    }
}

int main() {
    vector<int> arr = {1, -1, 2, -2, 3, -3};
    rearrangePartition(arr);
    for (int x : arr) cout << x << " ";
    // Output: -1 -2 -3 1 3 2
    return 0;
}

Python implementation

def rearrange_partition(arr):
    j = 0
    for i in range(len(arr)):
        if arr[i] < 0:
            arr[i], arr[j] = arr[j], arr[i]
            j += 1
    return arr

print(rearrange_partition([1, -1, 2, -2, 3, -3]))
# Output: [-1, -2, -3, 1, 3, 2]

This is also a useful pattern for in-place integer array manipulation. The boundary-pointer technique generalises to any condition, not just negative sign checks.

Complexity: O(n) time, O(1) space. One pass, no extra allocation.

Approach 2: Order-Preserving with Extra Space

When the interviewer says “preserve the relative order of both groups,” the clean O(n) solution uses a temporary array. Collect all negatives (in their original order), collect all positives (in their original order), then write both groups back into the original array.

The C++ equivalent is std::stable_partition, which guarantees the same order-preservation property in O(n log n) time (or O(n) if extra memory is available).

Step-by-step trace

Input: [1, -1, 2, -2, 3, -3]

• Collect negatives in order: [-1, -2, -3]
• Collect positives in order: [1, 2, 3]
• Concatenate: [-1, -2, -3, 1, 2, 3]
• Output: [-1, -2, -3, 1, 2, 3]

Both groups keep their original relative order.

C++ implementation

#include <iostream>
#include <vector>
using namespace std;

void rearrangeStable(vector<int>& arr) {
    vector<int> neg, pos;
    for (int x : arr) {
        if (x < 0) neg.push_back(x);
        else pos.push_back(x);
    }
    int k = 0;
    for (int x : neg) arr[k++] = x;
    for (int x : pos) arr[k++] = x;
}

int main() {
    vector<int> arr = {1, -1, 2, -2, 3, -3};
    rearrangeStable(arr);
    for (int x : arr) cout << x << " ";
    // Output: -1 -2 -3 1 2 3
    return 0;
}

Python implementation

def rearrange_order_preserving(arr):
    negatives = [x for x in arr if x < 0]
    positives = [x for x in arr if x >= 0]
    return negatives + positives

print(rearrange_order_preserving([1, -1, 2, -2, 3, -3]))
# Output: [-1, -2, -3, 1, 2, 3]

The space complexity here is O(n): the two temporary lists together hold every element once. For arrays of a few thousand elements that’s fine; for streaming data where memory is tight, you’d need the O(n^2) in-place insertion approach instead.

Approach 3: Alternating Arrangement

This variant places elements in interleaved order: one negative, one positive, one negative, one positive. If counts are unequal, the surplus goes at the end.

Step-by-step trace

Input: [1, -1, 2, -2, 3, -3]

• Collect negatives: [-1, -2, -3]
• Collect positives: [1, 2, 3]
• Interleave (negative first): -1, 1, -2, 2, -3, 3
• Output: [-1, 1, -2, 2, -3, 3]

For an unequal case, say [-1, -2, 3, 4, 5]:

• Negatives: [-1, -2]
• Positives: [3, 4, 5]
• Interleave: -1, 3, -2, 4, then append surplus 5.
• Output: [-1, 3, -2, 4, 5]

Python implementation

def rearrange_alternating(arr):
    negs = [x for x in arr if x < 0]
    pos  = [x for x in arr if x >= 0]
    result = []
    i, j = 0, 0
    while i < len(negs) and j < len(pos):
        result.append(negs[i]); i += 1
        result.append(pos[j]);  j += 1
    result += negs[i:] + pos[j:]
    return result

print(rearrange_alternating([1, -1, 2, -2, 3, -3]))
# Output: [-1, 1, -2, 2, -3, 3]
print(rearrange_alternating([-1, -2, 3, 4, 5]))
# Output: [-1, 3, -2, 4, 5]

Complexity Comparison and Interview Usage

Approach	Time	Space	Stable?	Use when
1: Partition in-place	O(n)	O(1)	No	Speed and memory matter; order is irrelevant
2: Order-preserving	O(n)	O(n)	Yes	Relative order of both groups must be preserved
3: Alternating	O(n)	O(n)	Yes	Interleaved output required

For input sizes common in placement tests, all three run fast enough that the difference in wall-clock time is invisible. The examiner is testing whether you recognise which variant is being asked and whether you state the trade-off before writing the code.

Related single-pass array problems worth knowing alongside this one: equilibrium index (one-pass prefix-sum) and symmetric pairs (hash-map approach). The two-pointer boundary technique from Approach 1 appears in all three problem families.

Service-tier companies typically ask for Approach 1 in the 20 to 30 minute coding round. A follow-up asking for order preservation signals Approach 2. Alternating arrangement appears less often, but it is a recurring question in off-campus drives run by mid-size IT firms.

The Lomuto partition pattern from Approach 1 shows up in production data pipelines too: splitting a batch of rows into valid and invalid before processing, filtering log entries by severity, or partitioning API responses by status code. TinkerLLM at ₹299 is where those kinds of patterns meet actual LLM preprocessing code; the playground includes filterable data pipelines students regularly adapt for their own projects.