Rearrange Array Elements by Sign — Editorial

Opening the reading…

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.

Approach

Create an answer array of the same length as nums, because fixed destination slots let you preserve order without shifting already written values.

Set pos to 0 and neg to 1, because index 0 must hold a positive value and index 1 must hold a negative value.

Scan every value x from left to right, because processing each sign in input order is what preserves the relative order within that sign.

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.

Otherwise, write x at ans[neg] and increase neg by 2, because the next valid negative destination is the next odd index.

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

MEASURE	BOUND	WHY
Time	O(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.
Space	O(1) extra	The 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.