Alternate Positive And Negative Numbers

Given an unsorted array arr containingbothpositive and negative numbers. Your task is to create an array of alternate positive and negative numbers without changing the relative order of positive and negative numbers.
Note: Array should start with a positive number and 0 (zero) should be considered a positive element.

Examples:

Input: arr[] = [9, 4, -2, -1, 5, 0, -5, -3, 2]
Output: 9 -2 4 -1 5 -5 0 -3 2
Explanation: Positive elements : [9,4,5,0,2]
Negative elements : [-2,-1,-5,-3]
As we need to maintain the relative order of postive elements and negative elements we will pick each element from the positive and negative and will store them. If any of the positive and negative numbersare completed. we will continue with the remaining signed elements.
The output is 9,-2,4,-1,5,-5,0,-3,2.

Input: arr[] = [-5, -2, 5, 2, 4, 7, 1, 8, 0, -8]
Output: 5 -5 2 -2 4 -8 7 1 8 0
Explanation : Positive elements : [5,2,4,7,1,8,0]
Negative elements : [-5,-2,-8]
The output is 5, -5, 2, -2, 4, -8, 7, 1, 8, 0.

Expected Time Complexity: O(n)
Expected Auxiliary Space: O(n)

Constraints:
1 ≤ arr.size() ≤ 10⁷
-10⁶ ≤ arr[i] ≤ 10⁷

Approach 01:

class Solution {
   public:

    void rearrange(vector<int> &arr) {
        vector<int> positiveNumbers, negativeNumbers;
        for(auto num : arr) {
            if(num >= 0) {
                positiveNumbers.push_back(num);
            } else {
                negativeNumbers.push_back(num);
            }
        }
        
        int positiveIndex = 0, negativeIndex = 0;
        vector<int> rearrangedArray;
        
        // Alternating between positive and negative numbers
        while (positiveIndex < positiveNumbers.size() && negativeIndex < negativeNumbers.size()) {
            rearrangedArray.push_back(positiveNumbers[positiveIndex++]);  
            rearrangedArray.push_back(negativeNumbers[negativeIndex++]);  
        }

        // Adding remaining positive numbers, if any
        while (positiveIndex < positiveNumbers.size()) {
            rearrangedArray.push_back(positiveNumbers[positiveIndex++]);
        }

        // Adding remaining negative numbers, if any
        while (negativeIndex < negativeNumbers.size()) {
            rearrangedArray.push_back(negativeNumbers[negativeIndex++]);
        }

        arr = rearrangedArray;  // Updating the original array
    }
};

class Solution:
    def rearrange(self, arr):
        positiveNumbers = []
        negativeNumbers = []

        # Separate positive and negative numbers
        for num in arr:
            if num >= 0:
                positiveNumbers.append(num)
            else:
                negativeNumbers.append(num)

        positiveIndex = 0
        negativeIndex = 0
        rearrangedArray = []

        # Alternating between positive and negative numbers
        while positiveIndex < len(positiveNumbers) and negativeIndex < len(negativeNumbers):
            rearrangedArray.append(positiveNumbers[positiveIndex])
            rearrangedArray.append(negativeNumbers[negativeIndex])
            positiveIndex += 1
            negativeIndex += 1

        # Adding remaining positive numbers, if any
        while positiveIndex < len(positiveNumbers):
            rearrangedArray.append(positiveNumbers[positiveIndex])
            positiveIndex += 1

        # Adding remaining negative numbers, if any
        while negativeIndex < len(negativeNumbers):
            rearrangedArray.append(negativeNumbers[negativeIndex])
            negativeIndex += 1

        # Updating the original array
        arr[:] = rearrangedArray

Time Complexity

• Separating Positive and Negative Numbers:

  The algorithm iterates over the input array once to separate the positive and negative numbers into two different vectors. This operation takes \(O(n)\), where n is the size of the input array.

• Alternating Positive and Negative Numbers:

  After separating the numbers, the algorithm combines them in alternating order, which requires a second pass over the arrays. Since both positive and negative numbers are processed once, this step also takes \(O(n)\).

• Overall Time Complexity:

  The overall time complexity is \(O(n)\), where n is the size of the input array.

Space Complexity

• Space for Positive and Negative Number Vectors:

  Two separate vectors, one for positive numbers and one for negative numbers, are used. Each of these vectors takes up \(O(n)\) space, where n is the size of the input array.

• Space for Rearranged Array:

  The rearranged array is another vector that also takes up \(O(n)\) space.

• Overall Space Complexity:

  The overall space complexity is \(O(n)\) because of the additional space used for the positive numbers, negative numbers, and rearranged array.