Problem Statement

Given an array of integers, rearrange its element such that positive and negative numbers appear alternatively, starting with a positive number. The relative order of positive numbers should remain the same as in the original array.

Examples

Example 1:

Input: arr[] = {1, -2, -3, -4, 5, 6}
Output: {1, -2, 5, -3, 6, -4}

Different Approaches

1️⃣ Brute Force Method

Intuition:

• This problem can be easily solved if O(N) extra space is required.
• We can store the positive values and negative values in two separate data structures.
• We will start filling the original array with alternating negative and positive values in the same order in which it appears in the original array.

Algorithm:

In this approach, We traverse the original array to segregate positive and negative elements into separate vectors.

We then initialize two indices, posIdx and negIdx to keep track of the positions in the positive and negative vectors, respectively.

We traverse the original array again and place positive elements at even indices and negative elements at odd indices.

Code:

#include <iostream>
#include <vector>
using namespace std;

void rearrangeArrayBySign(vector<int>& A) {
    vector<int> pos, neg;
    int n = A.size();
    
    // Segregate positive and negative elements
    for (int i = 0; i < n; ++i) {
        if (A[i] > 0)
            pos.push_back(A[i]);
        else
            neg.push_back(A[i]);
    }

    // Alternate placement
    int posIdx = 0, negIdx = 0;
    for (int i = 0; i < n; ++i) {
        if (i % 2 == 0 && posIdx < pos.size()) {
            A[i] = pos[posIdx];
            posIdx++;
        } else if (negIdx < neg.size()) {
            A[i] = neg[negIdx];
            negIdx++;
        }
    }
}

int main() {
    vector<int> A = {1, -2, 3, -4, 5, -6};
    
    rearrangeArrayBySign(A);
    
    cout << "Rearranged Array:";
    for (int num : A)
        cout << " " << num;
    cout << endl;
    
    return 0;
}


// Output

Rearranged Array: 1 -2 3 -4 5 -6

Complexity Analysis:

• Time Complexity:O(N + N)
  • First, O(N) for traversing the array once for segregating positives and negatives.
  • Another O(N) for adding those elements alternatively to the array.
• Space Complexity:O(N)
  • Space Required for each of the positive negative elements arrays.

2️⃣ Optimal Approach: To solve the problem in O(1) space

Intuition:

The optimal approach leverages a single traversal of the array to rearrange its elements by sign. We maintain two pointers, one for positive elements and other for negative elements. By ensuring these pointers point to the next available positive and negative elements respectively, we swap positive and negative elements found.

Code:

#include <iostream>
#include <vector>
using namespace std;

void rearrangeArrayBySign(vector<int>& A) {
    int n = A.size();
    
    // Initialize pointers for positive and negative elements
    int posIdx = 0;
    int negIdx = 1;
    
    // Rearrange elements
    while (posIdx < n && negIdx < n) {
        // Find the next positive element
        while (posIdx < n && A[posIdx] >= 0) 
            posIdx += 2;
        
        // Find the next negative element
        while (negIdx < n && A[negIdx] < 0)
            negIdx += 2;
        
        // Swap positive and negative elements if found
        if (posIdx < n && negIdx < n)
            swap(A[posIdx], A[negIdx]);
    }
}

int main() {
    vector<int> A = {1, -2, -3, 4, 5, -6};
    
    rearrangeArrayBySign(A);
    
    cout << "Rearranged Array:";
    for (int num : A)
        cout << " " << num;
    cout << endl;
    
    return 0;
}

Complexity Analysis:

• Time Complexity: O(N)
• Space Complexity: O(1)