Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Rearrange Array Elements by Sign

MEDIUMProblemSolveExternal Links

Description

You are given a 0-indexed integer array nums of even length consisting of an equal number of positive and negative integers.

You need to return the array after rearranging it so that it satisfies all of the following conditions:

  1. Every consecutive pair of integers has opposite signs.
  2. For all integers with the same sign, the order in which they appeared in the original array is preserved.
  3. The rearranged array begins with a positive integer.

In other words, interleave the positive and negative numbers while keeping their relative order intact, starting with a positive number.

Examples

Example 1

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

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

Explanation: The positive integers in nums are [3, 1, 2] and the negative integers are [-2, -5, -4]. We interleave them starting with a positive: take the first positive (3), then the first negative (-2), then the second positive (1), then the second negative (-5), and so on. The result is [3, -2, 1, -5, 2, -4]. Both the positive and negative subsequences retain their original relative order.

Example 2

Input: nums = [-1, 1]

Output: [1, -1]

Explanation: There is exactly one positive integer (1) and one negative integer (-1). Since the result must start with a positive integer, we place 1 first, then -1.

Example 3

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

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

Explanation: The array already satisfies all conditions — it alternates between positive and negative, starts with a positive, and the relative order within each sign group is preserved. No rearrangement is needed.

Constraints

  • 2 ≤ nums.length ≤ 2 × 10^5
  • nums.length is even
  • 1 ≤ |nums[i]| ≤ 10^5
  • nums consists of an equal number of positive and negative integers

Editorial

Brute Force

Intuition

The most natural approach is to separate the problem into two phases:

  1. Collect: Walk through the array and collect all positive numbers into one list and all negative numbers into another, maintaining their original order.
  2. Merge: Build the result by alternating — take the first positive, then the first negative, then the second positive, and so on.

Think of it like sorting two decks of colored cards. You first pick up all red cards into one pile and all blue cards into another (preserving the order you found them). Then you deal them out one by one, alternating red-blue-red-blue, starting with red.

This approach is straightforward because separating positives and negatives is a single pass, and merging them back is another single pass.

Step-by-Step Explanation

Let's trace through with nums = [3, 1, -2, -5, 2, -4]:

Phase 1: Separate positives and negatives

Step 1: Process nums[0] = 3. Positive → add to positives. positives = [3], negatives = [].

Step 2: Process nums[1] = 1. Positive → add to positives. positives = [3, 1], negatives = [].

Step 3: Process nums[2] = -2. Negative → add to negatives. positives = [3, 1], negatives = [-2].

Step 4: Process nums[3] = -5. Negative → add to negatives. positives = [3, 1], negatives = [-2, -5].

Step 5: Process nums[4] = 2. Positive → add to positives. positives = [3, 1, 2], negatives = [-2, -5].

Step 6: Process nums[5] = -4. Negative → add to negatives. positives = [3, 1, 2], negatives = [-2, -5, -4].

Phase 2: Merge alternately

Step 7: Take positives[0] = 3, negatives[0] = -2 → result = [3, -2].

Step 8: Take positives[1] = 1, negatives[1] = -5 → result = [3, -2, 1, -5].

Step 9: Take positives[2] = 2, negatives[2] = -4 → result = [3, -2, 1, -5, 2, -4].

Result: [3, -2, 1, -5, 2, -4]

Brute Force — Separate and Merge — Watch how we first separate positives and negatives into two lists, then merge them by alternating to build the result.

Algorithm

  1. Create two empty lists: positives and negatives
  2. Iterate through the array:
    • If the current element is positive, append it to positives
    • Otherwise, append it to negatives
  3. Create a result array of the same size
  4. For i from 0 to n/2 - 1:
    • Place positives[i] at result[2*i] (even index)
    • Place negatives[i] at result[2*i + 1] (odd index)
  5. Return the result array

Code

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> rearrangeArray(vector<int>& nums) {
        vector<int> positives, negatives;
        
        for (int num : nums) {
            if (num > 0) positives.push_back(num);
            else negatives.push_back(num);
        }
        
        int n = nums.size();
        vector<int> result(n);
        for (int i = 0; i < n / 2; i++) {
            result[2 * i] = positives[i];
            result[2 * i + 1] = negatives[i];
        }
        
        return result;
    }
};
class Solution:
    def rearrangeArray(self, nums: list[int]) -> list[int]:
        positives = [x for x in nums if x > 0]
        negatives = [x for x in nums if x < 0]
        
        result = [0] * len(nums)
        for i in range(len(positives)):
            result[2 * i] = positives[i]
            result[2 * i + 1] = negatives[i]
        
        return result
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int[] rearrangeArray(int[] nums) {
        List<Integer> positives = new ArrayList<>();
        List<Integer> negatives = new ArrayList<>();
        
        for (int num : nums) {
            if (num > 0) positives.add(num);
            else negatives.add(num);
        }
        
        int n = nums.length;
        int[] result = new int[n];
        for (int i = 0; i < n / 2; i++) {
            result[2 * i] = positives.get(i);
            result[2 * i + 1] = negatives.get(i);
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n)

We make two passes through the array: one to separate positives and negatives (O(n)), and one to merge them into the result (O(n/2)). Total: O(n).

Space Complexity: O(n)

We store all positives in one list (n/2 elements) and all negatives in another (n/2 elements), plus the result array of size n. Total extra space: O(n).

Why This Approach Is Not Efficient

While the brute force approach has optimal O(n) time complexity, it uses extra O(n) space for the two intermediate lists (positives and negatives). For arrays up to 2 × 10^5 elements, this extra memory is manageable but unnecessary.

The key insight: instead of separating into two lists and then merging, we can build the result in a single pass. If we maintain two pointers — one tracking the next position for a positive element (even indices: 0, 2, 4, ...) and one for a negative element (odd indices: 1, 3, 5, ...) — we can place each element directly into its correct position as we encounter it.

This eliminates the need for the two intermediate lists entirely, reducing the number of passes and simplifying the logic. Although the overall space is still O(n) for the result array (which is required by the problem), we avoid the extra O(n) overhead of the separation lists.

Optimal Approach - Two Index Placement

Intuition

Instead of separating and merging in two phases, we can do everything in one pass.

The key observation is simple: in the final result, all positive numbers occupy even indices (0, 2, 4, ...) and all negative numbers occupy odd indices (1, 3, 5, ...). So we maintain two pointers:

  • posIdx starts at 0 and jumps by 2 each time we place a positive number
  • negIdx starts at 1 and jumps by 2 each time we place a negative number

As we scan through the original array, each element is immediately placed at the correct position in the result array:

  • If positive → place at posIdx, then posIdx += 2
  • If negative → place at negIdx, then negIdx += 2

Think of it like filling two interleaved tracks simultaneously. One track runs through slots 0, 2, 4, ... and the other through 1, 3, 5, .... Each element self-selects its track based on its sign.

This approach is elegant because it preserves relative order automatically — elements within each sign group are encountered in their original order, and they are placed sequentially into their track.

Step-by-Step Explanation

Let's trace through with nums = [3, 1, -2, -5, 2, -4]:

Initialize: result = [_, _, _, _, _, _], posIdx = 0, negIdx = 1.

Step 1: nums[0] = 3 (positive). Place at result[posIdx=0]. result = [3, _, _, _, _, _]. posIdx → 2.

Step 2: nums[1] = 1 (positive). Place at result[posIdx=2]. result = [3, _, 1, _, _, _]. posIdx → 4.

Step 3: nums[2] = -2 (negative). Place at result[negIdx=1]. result = [3, -2, 1, _, _, _]. negIdx → 3.

Step 4: nums[3] = -5 (negative). Place at result[negIdx=3]. result = [3, -2, 1, -5, _, _]. negIdx → 5.

Step 5: nums[4] = 2 (positive). Place at result[posIdx=4]. result = [3, -2, 1, -5, 2, _]. posIdx → 6.

Step 6: nums[5] = -4 (negative). Place at result[negIdx=5]. result = [3, -2, 1, -5, 2, -4]. negIdx → 7.

Result: [3, -2, 1, -5, 2, -4]

One-Pass Two-Index Placement — Watch how two index pointers (posIdx for even slots, negIdx for odd slots) allow each element to be placed directly into its correct position in a single scan.

Algorithm

  1. Create a result array of size n
  2. Initialize posIdx = 0 (tracks next even-index slot for positives)
  3. Initialize negIdx = 1 (tracks next odd-index slot for negatives)
  4. For each element in the input array:
    • If element > 0: result[posIdx] = element, posIdx += 2
    • If element < 0: result[negIdx] = element, negIdx += 2
  5. Return the result array

Code

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> rearrangeArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> result(n);
        int posIdx = 0, negIdx = 1;
        
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                result[posIdx] = nums[i];
                posIdx += 2;
            } else {
                result[negIdx] = nums[i];
                negIdx += 2;
            }
        }
        
        return result;
    }
};
class Solution:
    def rearrangeArray(self, nums: list[int]) -> list[int]:
        n = len(nums)
        result = [0] * n
        pos_idx, neg_idx = 0, 1
        
        for num in nums:
            if num > 0:
                result[pos_idx] = num
                pos_idx += 2
            else:
                result[neg_idx] = num
                neg_idx += 2
        
        return result
class Solution {
    public int[] rearrangeArray(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        int posIdx = 0, negIdx = 1;
        
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                result[posIdx] = nums[i];
                posIdx += 2;
            } else {
                result[negIdx] = nums[i];
                negIdx += 2;
            }
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n)

We make exactly one pass through the input array. Each element is processed in O(1) time (one comparison and one assignment). Total: O(n).

Space Complexity: O(n)

We allocate a result array of size n. This is necessary because the problem requires returning a new array (not modifying in-place). No additional data structures are used beyond the result array — unlike the brute force, we do not create separate positives and negatives lists.

Note: If we ignore the output array (which is required), the extra working space is O(1) — just two integer pointers. This is the minimum possible for this problem since we must produce a rearranged copy of the input.