DSA SheetMedium
EditorialPractice

2 POINTERS › TWO POINTER ON ARRAYS

Rearrange Array Elements by Sign

MediumEditorial · 6 minGenerated by gpt-5.6-luna · Aug 26

Open — the attempt gate is not wired up yet

This editorial is meant to unlock after you have run the problem at least once, with the worked solution behind one further deliberate click. That needs per-learner unlock state nothing stores today, so for now the whole article is open.

Try it yourself first →

Intuitionthe required order is encoded by the destination indices

The result has a positive number at index 0, then a negative number at index 1, then a positive number at index 2, and so on. Because the array contains equally many positive and negative values, every even index is reserved for a positive value and every odd index is reserved for a negative value.

The remaining requirement is stability: positives must appear in the same order as they did in nums, and negatives must do the same. Scan nums from left to right. Each positive goes into the next unused even index, while each negative goes into the next unused odd index. Since each sign gets its own forward-moving destination, neither group is reordered.

An output array with separate positive and negative destination slotsThe drawing shows an output row indexed from 0 through n - 1. Even-indexed cells, beginning with cell 0, are marked for positive values, and odd-indexed cells, beginning with cell 1, are marked for negative values. A positive pointer starts at cell 0 and jumps two cells at a time; a negative pointer starts at cell 1 and also jumps two cells at a time. Values enter these destinations as the input is scanned from left to right, making each sign group stable.0 +1 −2 +3 −4 +5 −6 +7 −3+? no5−74−16−3Separate destinations preserve scan orderoutput arraypositive pointer p: 0 → 2 → 4 → 6 (step +2)negative pointer q: 1 → 3 → 5 → 7 (step +2)left-to-right input scanEach value takes the next slot of its sign; both streams keep their original relativeorder.

Approach

  1. Create an answer array of the same length as nums, because fixed destination slots let you preserve order without shifting already written values.
  2. Set pos to 0 and neg to 1, because index 0 must hold a positive value and index 1 must hold a negative value.
  3. Scan every value x from left to right, because processing each sign in input order is what preserves the relative order within that sign.
  4. If x is positive, write it at ans[pos] and increase pos by 2, because the next valid positive destination is the next even index.
  5. Otherwise, write x at ans[neg] and increase neg by 2, because the next valid negative destination is the next odd index.
  6. Return ans after the scan, because the equal counts guarantee that every even and odd destination has been filled exactly once.

Complexitythe output is required storage, not working memory

MEASUREBOUNDWHY
TimeO(n)The scan examines each input value once, and each value causes exactly one assignment to the answer. The destination pointers only move forward, so no index is revisited or shifted.
SpaceO(1) extraThe answer array uses O(n) storage but is required output and is excluded from the extra-space bound. Apart from it, the algorithm stores only two indices and one value, so the bound remains O(1) for every valid input shape.
Here n is the length of nums.

Annotated solutionC++ · one pass with parity-based destination pointers

CPPOne left-to-right scan writes positives to even indices and negatives to odd indices.
#include <vector>
using namespace std;

class Solution {
public:
    vector<int> rearrangeArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n);
        int pos = 0;
        int neg = 1;

        for (int x : nums) {
            if (x > 0) {
                ans[pos] = x;
                pos += 2;
            } else {
                ans[neg] = x;
                neg += 2;
            }
        }

        return ans;
    }
};

The important placement is not the sign test itself but the two destination pointers. Advancing pos and neg by two skips every slot reserved for the other sign. The scan order handles stability automatically: the first positive encountered occupies the first positive slot, the second occupies the next one, and the same argument applies to negatives.

The separate-lists alternativeclearer to derive, but it spends extra working memory

CPPA two-phase version that stores each sign in its own stable list before merging.
#include <vector>
using namespace std;

class Solution {
public:
    vector<int> rearrangeArray(vector<int>& nums) {
        vector<int> positives;
        vector<int> negatives;

        for (int x : nums) {
            if (x > 0) {
                positives.push_back(x);
            } else {
                negatives.push_back(x);
            }
        }

        vector<int> ans(nums.size());
        int index = 0;
        for (int i = 0; i < static_cast<int>(positives.size()); ++i) {
            ans[index++] = positives[i];
            ans[index++] = negatives[i];
        }

        return ans;
    }
};

This version is a different arrangement, not an optimisation. It can be easier to understand because separation and merging are visible as two distinct phases, and the equal counts make the merge loop straightforward. Its time remains O(n), but the positive and negative lists use O(n) extra space in addition to the required answer array. The one-pass pointer version avoids that storage without sacrificing readability.

Common mistakesthe wrong line usually preserves one requirement while breaking another

Previous · Sort Array by Parity II