Skip to main content

Two Pointer

Rearrange Array Elements by Sign

Problem Description

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

You should return the array of nums such that the array follows the given conditions:

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

Return the modified array after rearranging the elements to satisfy the aforementioned conditions.

Example

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]. The negative integers are [-2,-5,-4].
The only possible way to rearrange them such that they satisfy all conditions is [3,-2,1,-5,2,-4].
Other ways such as [1,-2,2,-5,3,-4], [3,1,2,-2,-5,-4], [-2,3,-5,1,-4,2] are incorrect because they do not satisfy one or more conditions.

Example 2:

Input: nums = [-1,1]
Output: [1,-1]
Explanation:
1 is the only positive integer, and -1 is the only negative integer in nums.
So nums is rearranged to [1,-1]. 

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.

It is not required to do the modifications in place.

💡
Try Solving Rearrange Array Elements by Sign Yourself First !!
Let's tackle the problem “Rearrange Array Elements by Sign” step by step. We'll start by understanding the most intuitive solution and then work our way toward a more optimized approach, if one exists. So, grab a pen and paper, and let's break down the algorithm together!

Brute force Approach

Intuition

If we break down this problem, we are given an array that contains an equal number of positive and negative integers. The task is to rearrange the array such that:

  • Positive and negative numbers alternate in the array.
  • The relative order of positive and negative numbers must be preserved.
  • The array should start with a positive number.

Now, if we observe carefully, we know that if we separate both positive and negative integers from our array into separate lists, then we can alternate them easily as mentioned in the question.

So, to store our positive and negative numbers separately, we can assign them to two different lists. Now once we have them in two separate lists, we can start picking elements from each list one by one, placing them alternately in the result array. This ensures two things:

  1. The alternating order (positive, negative, positive, negative, etc.) is maintained.
  2. The relative ordering of numbers in their original group (positive or negative) is preserved.

Example:
Let's take an array:
nums = [3, -2, 1, -5, 2, -4]
Separate into:
pos = [3, 1, 2]
neg = [-2, -5, -4]

Now, fill the result array:
ans[0] = 3, ans[1] = -2
ans[2] = 1, ans[3] = -5
ans[4] = 2, ans[5] = -4

Final output: [3, -2, 1, -5, 2, -4]
This is our final answer.

Rearrange Array Elements by Sign Algorithm

Steps:

  1. Initialize Two Lists:
    • Create two empty lists: pos[] for positive numbers and neg[] for negative numbers.
  2. Separate the Elements:
    • For each element i in nums[]:
      • If i is positive, append it to pos[].
      • Else, append it to neg[].
  3. Initialize the Result Array:
    • Create a new array ans[] of the same size n.
    • Set two pointers: idx = 0 (to track the index in ans[]) and i = 0 (to track the index in pos[] and neg[]).
  4. Fill the Result Array Alternately:
    • While idx < n - 1:
      • Set ans[idx] = pos[i] (Place positive number at even index).
      • Set ans[idx + 1] = neg[i] (Place negative number at odd index).
      • Increment both idx by 2 and i by 1.
  5. Return the Result:
  • Return the ans[] array as the final output.

Dry-Run

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

Step 1: Separate Positive and Negative Numbers

  • Initialize two lists: pos = [], neg = []
  • Loop through each element of nums:
    • 3 is positive → add to pos → pos = [3]
    • -2 is negative → add to neg → neg = [-2]
    • 1 is positive → add to pos → pos = [3, 1]
    • -5 is negative → add to neg → neg = [-2, -5]
    • 2 is positive → add to pos → pos = [3, 1, 2]
    • -4 is negative → add to neg → neg = [-2, -5, -4]

Step 2: Fill the Result Array Alternately

  • Initialize the result array ans = [0, 0, 0, 0, 0, 0]
  • Initialize pointers: `idx = 0, `i = 0

First iteration:

  • Place pos[0] = 3 at ans[0]
  • Place neg[0] = -2 at ans[1]
  • Result now: ans = [3, -2, 0, 0, 0, 0]
  • Increment: idx = 2, i = 1

Second iteration:

  • Place pos[1] = 1 at ans[2]
  • Place neg[1] = -5 at ans[3]
  • Result now: ans = [3, -2, 1, -5, 0, 0]
  • Increment: idx = 4, i = 2

Third iteration:

  • Place pos[2] = 2 at ans[4]
  • Place neg[2] = -4 at ans[5]
  • Result now: ans = [3, -2, 1, -5, 2, -4]

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

Rearrange Array Elements by Sign Solution

Now let's check out the Rearrange Array Elements by Sign in C++, Java, Python and JavaScript.

Rearrange Array Elements by Sign Code in all Languages.
1. Rearrange Array Elements by Sign solution in C++ Try on Compiler 
#include <iostream>
#include <vector>
using namespace std;
 
// Function to rearrange array
vector<int> rearrangeArray(vector<int>& nums) {
    // Get the length of the array
    int n = nums.size();
 
    // Separate positive and negative numbers
    vector<int> pos, neg;
    for (int i : nums) {
        if (i < 0)
            neg.push_back(i);
        else
            pos.push_back(i);
    }
 
    // Create a result array of size n
    vector<int> ans(n);
 
    // Initialize index pointers
    int idx = 0, i = 0;
 
    // Fill alternating positive and negative values
    while (idx < n - 1) {
        ans[idx] = pos[i];
        ans[idx + 1] = neg[i];
        idx += 2;
        i++;
    }
 
    // Return the result
    return ans;
}
 
// Main function
int main() {
    // Take input from user
    int n;
    cin >> n;
 
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
 
    // Call the function
    vector<int> result = rearrangeArray(nums);
 
    // Print the result
    for (int i : result) {
        cout << i << " ";
    }
 
    return 0;
}

2. Rearrange Array Elements by Sign Solution in Java Try on Compiler 
import java.util.*;
 
public class Main {
 
    // Function to rearrange the array
    public static int[] rearrangeArray(int[] nums) {
        // Get the length of the array
        int n = nums.length;
 
        // Separate positive and negative numbers
        ArrayList<Integer> pos = new ArrayList<>();
        ArrayList<Integer> neg = new ArrayList<>();
        for (int i : nums) {
            if (i < 0)
                neg.add(i);
            else
                pos.add(i);
        }
 
        // Create a result array of size n
        int[] ans = new int[n];
 
        // Initialize index pointers
        int idx = 0, i = 0;
 
        // Fill alternating positive and negative values
        while (idx < n - 1) {
            ans[idx] = pos.get(i);
            ans[idx + 1] = neg.get(i);
            idx += 2;
            i++;
        }
 
        // Return the result
        return ans;
    }
 
    // Main function
    public static void main(String[] args) {
        // Take input from user
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
 
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
 
        // Call the function
        int[] result = rearrangeArray(nums);
 
        // Print the result
        for (int i : result) {
            System.out.print(i + " ");
        }
    }
}

3. Rearrange Array Elements by Sign in Python Try on Compiler 
# Function to rearrange the array
def rearrange_array(nums):
    # Get the length of the array
    n = len(nums)
 
    # Separate positive and negative numbers
    pos = []
    neg = []
    for i in nums:
        if i < 0:
            neg.append(i)
        else:
            pos.append(i)
 
    # Create a result array of size n
    ans = [0] * n
 
    # Initialize index pointers
    idx = 0
    i = 0
 
    # Fill alternating positive and negative values
    while idx < n - 1:
        ans[idx] = pos[i]
        ans[idx + 1] = neg[i]
        idx += 2
        i += 1
 
    # Return the result
    return ans
 
# Main function
def main():
    # Take input from user
    n = int(input())
    nums = list(map(int, input().split()))
 
    # Call the function
    result = rearrange_array(nums)
 
    # Print the result
    print(result)
 
# Run the main function
if __name__ == "__main__":
    main()

4. Rearrange Array Elements by Sign solution in JavaScript Try on Compiler 
// Function to rearrange the array
function rearrangeArray(nums) {
    let n = nums.length;

    let pos = [], neg = [];
    for (let i of nums) {
        if (i < 0)
            neg.push(i);
        else
            pos.push(i);
    }

    let ans = new Array(n);
    let idx = 0, i = 0;

    while (idx < n - 1) {
        ans[idx] = pos[i];
        ans[idx + 1] = neg[i];
        idx += 2;
        i++;
    }

    return ans;
}

// Main function using readline
const readline = require("readline");

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let lines = [];
rl.on("line", (input) => {
    lines.push(input.trim());
    if (lines.length === 2) {
        let n = parseInt(lines[0]);
        let nums = lines[1].split(" ").map(Number);
        let result = rearrangeArray(nums);
        console.log(...result);
        rl.close();
    }
});

Rearrange Array Elements by Sign Complexity Analysis

Time Complexity: O(n)

Outer Loop (Separation): O(n)
The loop runs from index i = 0 to i = n - 1, iterating over each element of the input array.
Let’s denote:

  • n = number of elements in the input array

So, the loop executes n times, which is O(n).

Inner Access and Assignment Operations: O(1)
For each iteration, adding elements to ArrayLists and performing conditional checks are constant-time operations — O(1) each.

While Loop (Reconstruction): O(n)
The loop executes approximately n/2 times (two assignments per iteration).
Each access to ArrayList.get(i) and assignment to the result array takes O(1) time.
Thus, total time for the loop is O(n).

Input Reading Loop: O(n)
Reading n elements from input takes O(n) time.

Output Printing Loop: O(n)
Printing n elements from the result array takes O(n) time.

Final Time Complexity: O(n)
We perform O(1) operations for each of the O(n) elements during separation, rearranging, and printing.
So, the total time complexity is: O(n)

Where:

  • n is the number of elements in the input array.

Space Complexity: O(n)

Auxiliary Space Complexity: O(n)

This refers to any extra space used by the algorithm that is independent of the input and output space.
In this approach, we create:

  • Two ArrayLists to separately store positive and negative elements, together using O(n) space.
  • A result array of size n → O(n)
  • A few integer variables → O(1)

Therefore, the auxiliary space used is O(n).

Total Space Complexity: O(n)

This includes the space required for:

  • Input space: The input array of length n → O(n)
  • Output space: The result array of length n → O(n)
  • Extra space used by the algorithm: As analyzed above → O(n)

Combining all the space requirements:

Total Space Complexity = O(n) + O(n) + O(n) = O(n)

Where:

  • n is the number of elements in the input array.
This is an optimal solution for this question, but we are using extra space 3*O(n). Is there any approach to addressing this question without using extra space to separate the arrays in the positive and negative lists?

Optimal Approach

Intuition

In the above approach, we separated all positive and negative numbers into two separate lists and merged them back into the result array alternately.

Now, if we somehow reduce the time to separate our array into positive and negative lists, then we can reduce the overall time complexity from 2*O(n) to O(n).

So, if we look at our answer array, our observation is that all the positive numbers are at even indices and all the negative numbers are at odd indices.

Now, if we go to the first element in the array and ask whether it is positive or negative, then we can place it in its correct position in the result array at an even index or an odd index. If we do the same for all the elements in the array and simultaneously move the pointer at the even or odd index, then we can place all elements in their correct positions.

So, to do this, we use two pointers to keep track of positive and negative indices and iterate over our array once to place each element into its correct index in the answer array. This makes our solution even more efficient and cleaner.

For example, let's take an array :

nums = [3, -2, 1, -5, 2, -4]
Now, let's initialize our pointers at 0 and 1 indices respectively and our res array

pos = 0

neg = 1

res = [ ]

Now, let's start iterating over the array,

  • i = 0, nums[0] = 3 → This is a positive number
    → Place it at the index pos = 0 in res
    → res = [3, _, _, _, _, _]
    → Move pos pointer forward by 2 → pos = 2
  • i = 1, nums[1] = -2 → This is a negative number
    → Place it at the index neg = 1 in res
    → res = [3, -2, _, _, _, _]
    → Move neg pointer forward by 2 → neg = 3
  • i = 2, nums[2] = 1 → This is a positive number
    → Place it at the index pos = 2 in res
    → res = [3, -2, 1, _, _, _]
    → Move pos pointer forward by 2 → pos = 4
  • i = 3, nums[3] = -5 → This is a negative number
    → Place it at the index neg = 3 in res
    → res = [3, -2, 1, -5, _, _]
    → Move neg pointer forward by 2 → neg = 5
  • i = 4, nums[4] = 2 → This is a positive number
    → Place it at the index pos = 4 in res
    → res = [3, -2, 1, -5, 2, _]
    → Move pos pointer forward by 2 → pos = 6
  • i = 5, nums[5] = -4 → This is a negative number
    → Place it at the index neg = 5 in res
    → res = [3, -2, 1, -5, 2, -4]
    → Move neg pointer forward by 2 → neg = 7

We have now processed all elements.

Final rearranged array:

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

Rearrange Array Elements by Sign Algorithm

Steps:

  • Initialize Index Pointers:
    • Set two pointers:
      • pos = 0 → to track the next even index for a positive number.
      • neg = 1 → to track the next odd index for a negative number.
  • Initialize the Result Array:
    • Create a new array res[] of the same length as the input array nums[].
  • Iterate Over the Input Array:
    • For each element nums[i] in the input array:
      • If nums[i] a positive number:
        • Place it at the index pos in res[].
        • Increment pos by 2 (to go to the next even index).
      • Else (if nums[i] is a negative number):
        • Place it at the index neg in res[].
        • Increment neg by 2 (to go to the next odd index).
  • Return the Result:
    • Return the array res[] as the final rearranged result.

Dry-Run

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

Initial Setup:

pos = 0
neg = 1
res = [0, 0, 0, 0, 0, 0]

Iterating through nums:

1. nums[0] = 3 → Positive
• Place 3 at res[0]
• res = [3, 0, 0, 0, 0, 0]
• Increment pos → pos = 2

2. nums[1] = -2 → Negative
• Place -2 at res[1]
• res = [3, -2, 0, 0, 0, 0]
• Increment neg → neg = 3

3. nums[2] = 1 → Positive
• Place 1 at res[2]
• res = [3, -2, 1, 0, 0, 0]
• Increment pos → pos = 4

4. nums[3] = -4 → Negative
• Place -4 at res[3]
• res = [3, -2, 1, -4, 0, 0]
• Increment neg → neg = 5

5. nums[4] = -1 → Negative
• Place -1 at res[5]
• res = [3, -2, 1, -4, 0, -1]
• Increment neg → neg = 7

6. nums[5] = 2 → Positive
• Place 2 at res[4]
• res = [3, -2, 1, -4, 2, -1]
• Increment pos → pos = 6

Final Result:

res = [3, -2, 1, -4, 2, -1]

Rearrange Array Elements by Sign Solution

Now lets checkout the Rearrange Array Elements by Signcode in C++ , Java, Python and JavaScript.

Rearrange Array Elements by Sign Code in all Languages.
1. Rearrange Array Elements by Sign solution in C++ Try on Compiler 
#include <iostream>
#include <vector>
using namespace std;
 
// Function to rearrange array
vector<int> rearrangeArray(vector<int>& arr) {
    // Initialize pointers for positive and negative indices
    int pos = 0, neg = 1;
   
    // Initialize result array with same size as input
    vector<int> result(arr.size());
 
    // Traverse through original array
    for(int i = 0; i < arr.size(); i++) {
        // If current element is positive, place at even index
        if(arr[i] > 0) {
            result[pos] = arr[i];
            pos += 2;
        }
        // If current element is negative, place at odd index
        else {
            result[neg] = arr[i];
            neg += 2;
        }
    }
 
    // Return the rearranged result array
    return result;
}
 
int main() {
    // Take input from user
    int n;
    cin >> n;
   
    vector<int> nums(n);
    for(int i = 0; i < n; i++) {
        cin >> nums[i];
    }
 
    // Call rearrangeArray function
    vector<int> result = rearrangeArray(nums);
 
    // Print the output array
    for(int num : result) {
        cout << num << " ";
    }
    cout << endl;
 
    return 0;
}

2. Rearrange Array Elements by Sign Solution in Java Try on Compiler 
import java.util.*;
 
public class Main {
 
    // Function to rearrange array
    public static int[] rearrangeArray(int[] arr) {
        // Initialize pointers for positive and negative indices
        int pos = 0, neg = 1;
 
        // Create a result array of same size
        int[] result = new int[arr.length];
 
        // Traverse through original array
        for (int i = 0; i < arr.length; i++) {
            // If positive number, put at even index
            if (arr[i] > 0) {
                result[pos] = arr[i];
                pos += 2;
            }
            // Else put negative at odd index
            else {
                result[neg] = arr[i];
                neg += 2;
            }
        }
 
        // Return result array
        return result;
    }
 
    public static void main(String[] args) {
        // Take input from user
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
 
        // Call rearrangeArray method
        int[] result = rearrangeArray(arr);
 
        // Print result array
        for (int num : result) {
            System.out.print(num + " ");
        }
    }
}

3. Rearrange Array Elements by Sign Solution in Python Try on Compiler 
# Function to rearrange array
def rearrange_array(arr):
    # Initialize pointers
    pos = 0
    neg = 1

    # Create result array of same length
    result = [0] * len(arr)

    # Traverse through the original array
    for num in arr:
        # Place positive number at even index
        if num > 0:
            result[pos] = num
            pos += 2
        # Place negative number at odd index
        else:
            result[neg] = num
            neg += 2

    return result

# Take input from user
n = int(input())
arr = list(map(int, input().split()))

# Call function and print result
result = rearrange_array(arr)
print(result)

4. Rearrange Array Elements by Sign solution in JavaScript Try on Compiler 
// Function to rearrange array
function rearrangeArray(arr) {
    let result = new Array(arr.length);
    let pos = 0, neg = 1;

    for (let i = 0; i < arr.length; i++) {
        if (arr[i] > 0) {
            result[pos] = arr[i];
            pos += 2;
        } else {
            result[neg] = arr[i];
            neg += 2;
        }
    }

    return result;
}

// Read input using readline
const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let inputLines = [];
rl.on('line', (line) => {
    inputLines.push(line.trim());
    if (inputLines.length === 2) {
        const n = parseInt(inputLines[0]);
        const arr = inputLines[1].split(' ').map(Number);
        const result = rearrangeArray(arr);
        console.log(result.join(' '));
        rl.close();
    }
});

Rearrange Array Elements by Sign Complexity Analysis

Time Complexity: O(n)

Outer Loop: O(n)
The loop runs from index i = 0 to i = arr.length - 1.
Let’s denote:

  • n = length of the input array arr

So, the loop executes n times, which is O(n).

Operations Inside the Loop: O(1)
For each iteration:

  • Checking if arr[i] > 0 takes O(1)
  • Assigning value to result[pos] or result[neg] takes O(1)
  • Incrementing pos or neg by 2 takes O(1)

Thus, total cost per iteration = O(1)

Total Time per Outer Loop Iteration: O(1)
Each iteration performs constant time operations.

Final Time Complexity: O(n)
We perform O(1) operations for each of the O(n) elements in the array.
So, the total time complexity is: O(n)

Where:

  • n is the number of elements in the input array arr.

Space Complexity: O(n)

Auxiliary Space Complexity: O(n)

This refers to any extra space used by the algorithm that is independent of the input and output space.
In our approach, we create:

  • A new result array of the same size as the input array arr, i.e., of length n.
  • Two integer pointers pos and neg, which take constant space.

The result array requires space proportional to n, and the pointers take constant space.
Therefore, the auxiliary space used is O(n).

Total Space Complexity: O(n)

This includes the space required for:

  • Input space: The input array arr is of length n, so the input space is O(n).
  • Output space: We return a result array of length n, which is also O(n).
  • Extra space used by the algorithm: As analyzed above, O(n).

Combining all the space requirements:

Total Space Complexity = O(n) + O(n) + O(n) = O(n)

Where:

  • n is the number of elements in the input array arr.

Conclusion

We used two ways to solve this problem. The first approach collects positive and negative numbers separately and then merges them, while the second uses two pointers to place them directly into the result array. Both run in linear time and use extra space, but the second method is simpler and more efficient since it skips the extra step of storing numbers separately. It’s usually the better choice in real situations.

Similar Problems

Sort Array By Parity II

Given an array of integers nums, half of the integers in nums are odd, and the other half are even.

Sort the array so that whenever nums[i] is odd, i is odd, and whenever nums[i] is even, i is even.

Return any answer array that satisfies this condition.

Wiggle Subsequence

A wiggle sequence is a sequence where the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with one element and a sequence with two non-equal elements are trivially wiggle sequences.

  • For example, [1, 7, 4, 9, 2, 5] is a wiggle sequence because the differences (6, -3, 5, -7, 3) alternate between positive and negative.
  • In contrast, [1, 4, 7, 2, 5] and [1, 7, 4, 5, 5] are not wiggle sequences. The first is not because its first two differences are positive, and the second is not because its last difference is zero.

A subsequence is obtained by deleting some elements (possibly zero) from the original sequence, leaving the remaining elements in their original order.

Given an integer array nums, return the length of the longest wiggle subsequence of nums.

Partition Array According to Given Pivot

You are given a 0-indexed integer array nums and an integer pivot. Rearrange nums such that the following conditions are satisfied:

  • Every element less than pivot appears before every element greater than pivot.
  • Every element equal to pivot appears in between the elements less than and greater than pivot.
  • The relative order of the elements less than pivot and the elements greater than pivot is maintained.
    • More formally, consider every pi, pj where pi is the new position of the ith element and pj is the new position of the jth element. If i < j and both elements are smaller (or larger) than pivot, then pi < pj.

Return nums after the rearrangement.

Largest Number After Digit Swaps by Parity

You are given a positive integer num. You may swap any two digits of num that have the same parity (i.e. both odd digits or both even digits).

Return the largest possible value of num after any number of swaps.