Rearrange Array Elements by Sign

medium array two pointers simulation

Problem

Given an array nums of equal numbers of positive and negative integers, rearrange so that every consecutive pair has opposite signs, the order of positives among themselves is preserved, and the same for negatives. The result must start with a positive.

Inputnums = [3, 1, -2, -5, 2, -4]

Output[3, -2, 1, -5, 2, -4]

Positives 3,1,2 go to indices 0,2,4. Negatives -2,-5,-4 go to indices 1,3,5.

nums (comma-separated)

def rearrange_array(nums):
    n = len(nums)
    out = [0] * n
    pos, neg = 0, 1
    for x in nums:
        if x > 0:
            out[pos] = x
            pos += 2
        else:
            out[neg] = x
            neg += 2
    return out

function rearrangeArray(nums) {
  const n = nums.length;
  const out = new Array(n).fill(0);
  let pos = 0, neg = 1;
  for (const x of nums) {
    if (x > 0) {
      out[pos] = x;
      pos += 2;
    } else {
      out[neg] = x;
      neg += 2;
    }
  }
  return out;
}

class Solution {
    public int[] rearrangeArray(int[] nums) {
        int n = nums.length;
        int[] out = new int[n];
        int pos = 0, neg = 1;
        for (int x : nums) {
            if (x > 0) {
                out[pos] = x;
                pos += 2;
            } else {
                out[neg] = x;
                neg += 2;
            }
        }
        return out;
    }
}

vector<int> rearrangeArray(vector<int>& nums) {
    int n = nums.size();
    vector<int> out(n, 0);
    int pos = 0, neg = 1;
    for (int x : nums) {
        if (x > 0) {
            out[pos] = x;
            pos += 2;
        } else {
            out[neg] = x;
            neg += 2;
        }
    }
    return out;
}

Explanation

The result must alternate signs and start positive, so positives belong at even indices (0, 2, 4, ...) and negatives at odd indices (1, 3, 5, ...). We can fill those slots directly with two write pointers.

We make an output array out and keep pos = 0 (next even slot) and neg = 1 (next odd slot). Then we scan the input once.

When we see a positive number, we drop it at out[pos] and bump pos by 2 to the next even slot. When we see a negative, we drop it at out[neg] and bump neg by 2. Because we read the input in order, the positives keep their original relative order, and so do the negatives.

Example: nums = [3, 1, -2, -5, 2, -4]. Positives 3, 1, 2 land at indices 0, 2, 4; negatives -2, -5, -4 land at 1, 3, 5, producing [3, -2, 1, -5, 2, -4].

Since the counts of positives and negatives are equal, the two pointers fill all slots perfectly without colliding.

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