Rearrange Positive and Negative Numbers Alternatively in Array

Problem Statement

In the “Rearrange Positive and Negative Numbers Alternatively in Array” problem we have given an array a[]. This array contains positive and negative integers. Rearrange the array in such a way that positive and negative are placed alternatively. Here, the number of positive and negative elements need not be equal.

Note: If there are more positive or negative elements then they appear at the end of the array.

Input Format

The first and only one line containing an integer N.

Second-line containing N space-separated integers.

Output Format

The first and only one line containing N space-separated integer.

Constraints

• 1<=N<=10^5
• -10^9<=N<=10^9

Example

7
-5 -7 9 11 12 -15 17

-5 11 -15 17 -7 12 9

Explanation: Rearranged positives and negatives in alternative positions and excess in the end.

8
-4 -7 9 11 -16 13 3 -5

-16 11 -4 3 -7 13 -5 9

Explanation: Rearranged positives and negatives in alternative positions.

Algorithm

Here, we rearrange all positives at odd indices and negatives at even indices. The algorithm we follow is written below.

1. We modify the array such that all positives will be in the beginning of the array. And all the negative elements at the end.
   [1, -2, 3, 4, 5, -6, 7, 8, -9] → [1, 3, 4, 5, 7, 8, -2, -6, -9]
2. We maintain two pointers i and j. If array[j] > 0 we move it to the front of the array by a swap with the first element. Else we move forward.
3. We initialize negative numbers start index as negative and positive as 0.
4. Increment the negative index by 1 and the positive index by 2. That means we swap every alternate positive number with the next negative number.

Implementation

C++ Program for Rearrange Positive and Negative Numbers Alternatively in Array

#include <bits/stdc++.h>
using namespace std;

//Rearrange function  
void Rearrange(int array[], int n)
{
    int i = -1;
    //swap positive elements to the start of the array
    for (int j = 0; j < n; j++)
    {
        if (array[j] > 0)
        {
            i = i + 1;
            swap(array[i], array[j]);
        }
    }
    //Initialize positive_index, negative_index
    int positive_index = 0, negative_index = i + 1;
    //Increment postive by 2 and negative by 1.
    //swap elements after each increments and swap them.
    //such that alternative elements will be changed
    while (negative_index < n && negative_index > positive_index && array[negative_index] < 0)
    {
        swap(array[negative_index], array[positive_index]);
        positive_index = positive_index + 2;
        negative_index = negative_index + 1;
    }
}
 
int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    Rearrange(a,n);
    for(int i=0;i<n;i++)
    {
        cout<<a[i]<<" ";
    }
    return 0;
}

Java Program for Rearrange Positive and Negative Numbers Alternatively in Array

import java.util.Scanner;
class sum
{
    //Rearrange function  
    public static void Rearrange(int array[], int n)
    {
        int i = -1;
        //swap positive elements to the start of the array
        for (int j = 0; j < n; j++)
        {
            if (array[j] > 0)
            {
                i = i + 1;
                array[i] = (array[i] + array[j]) - (array[j] = array[i]);
            }
        }
        //Initialize positive_index, negative_index
        int positive_index = 0, negative_index = i + 1;
        //Increment postive by 2 and negative by 1.
        //swap elements after each increments and swap them.
        //such that alternative elements will be changed
        while (negative_index < n && negative_index > positive_index && array[negative_index] < 0)
        {
            array[negative_index] = (array[negative_index] + array[positive_index]) - (array[positive_index] = array[negative_index]);
            positive_index = positive_index + 2;
            negative_index = negative_index + 1;
        }
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        Rearrange(a, n);
        for(int i=0;i<n;i++)
        {
            System.out.print(a[i]+" ");
        }
    }
}

5
-1 -2 -3 4 5

-3 5 -1 4 -2

Complexity Analysis for Rearrange Positive and Negative Numbers Alternatively in Array

Time Complexity

O(n) where n is the size of the given array. Here we simply traverse the whole array and perform some operations which take constant time.

Space Complexity

O(1) because here we simply changed the positions of elements. We do not use any auxiliary space.