Given an array arr[] of size n, the task is to rearrange it in alternate positive and negative manner without changing the relative order of positive and negative numbers. In case of extra positive/negative numbers, they appear at the end of the array.

Note: The rearranged array should start with a positive number and 0 (zero) should be considered as a positive number.

Examples:

Input: arr[] = [1, 2, 3, -4, -1, 4]
Output: arr[] = [1, -4, 2, -1, 3, 4]
Input: arr[] = [-5, -2, 5, 2, 4, 7, 1, 8, 0, -8]
Output: arr[] = [5, -5, 2, -2, 4, -8, 7, 1, 8, 0]

Try it on GfG Practice

The idea is to separate the numbers into positive and negative arrays. Then, alternately place numbers from each array back into the original array. Also place any remaining positive or negative numbers at the end.

Working of Code With Example :

1. Let us consider arr = [1, 2, 3, -4, -1, 4]

2. First we create two vectors to store positive and negative numbers of the given array

pos[] = [1, 2, 3, 4], neg[] = [-4, -1]

4. Now we traverse both pos[] and neg[] and fill elements back into arr[] at alternate indexs

i = 0, Since i is even, we pick from pos, arr = [1, _, _, _, _, _]
i = 1, Since i is odd, we pick from neg, arr = [1, -4, _, _, _, _]
i = 2, Since i is even, we pick from pos, arr = [1, -4, 2, _, _, _]
i = 3, Since i is odd, we pick from neg, arr = [1, -4, 2, -1, _, _]

5. One List Exhausted, neg[] in this case, so we put remaining pos[] elements

Remaining pos[] = [3, 4]
Final arr[] = [1, -4, 2, -1, 3, 4]

C++

// C++ program to rearrange positive and negative numbers 
// alternately using Two pointers 
#include <iostream>
#include <vector>
using namespace std;

// Function to rearrange positive and negative numbers
// in alternate fashion
void rearrange(vector<int>& arr) {
    vector<int> pos, neg;

    // Separate positive and negative numbers
    for (int i = 0; i < arr.size(); i++) {
        if (arr[i] >= 0)
            pos.push_back(arr[i]);
        else
            neg.push_back(arr[i]);
    }

    int posIdx = 0, negIdx = 0;
    int i = 0;

    // Place positive and negative numbers alternately
    // in the original array
    while (posIdx < pos.size() && negIdx < neg.size()) {
        if (i % 2 == 0)
            arr[i++] = pos[posIdx++];
        else 
            arr[i++] = neg[negIdx++];
    }

    // Append remaining positive numbers (if any)
    while (posIdx < pos.size())
        arr[i++] = pos[posIdx++];

    // Append remaining negative numbers (if any)
    while (negIdx < neg.size())
        arr[i++] = neg[negIdx++];
}

int main() {
    vector<int> arr = {1, 2, 3, -4, -1, 4};
    rearrange(arr);
    for (int i = 0; i < arr.size(); i++) 
        cout << arr[i] << " ";

    return 0;
}

// C program to rearrange positive and negative numbers 
// alternately using Two pointers 

#include <stdio.h>

// Function to rearrange positive and negative numbers
// in alternate fashion
void rearrange(int arr[], int n) {
    int pos[n];
    int neg[n];
    int posCount = 0, negCount = 0;

    // Separate positive and negative numbers
    for (int i = 0; i < n; i++) {
        if (arr[i] >= 0)
            pos[posCount++] = arr[i];
        else
            neg[negCount++] = arr[i];
    }

    int posIdx = 0, negIdx = 0;
    int i = 0;

    // Place positive and negative numbers alternately
    // in the original array
    while (posIdx < posCount && negIdx < negCount) {
        if (i % 2 == 0)
            arr[i++] = pos[posIdx++];
        else 
            arr[i++] = neg[negIdx++];
    }

    // Append remaining positive numbers (if any)
    while (posIdx < posCount)
        arr[i++] = pos[posIdx++];

    // Append remaining negative numbers (if any)
    while (negIdx < negCount)
        arr[i++] = neg[negIdx++];
}

int main() {
    int arr[] = {1, 2, 3, -4, -1, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    rearrange(arr, n);
    for (int i = 0; i < n; i++) 
        printf("%d ", arr[i]);
    
    return 0;
}

Java

// Java program to rearrange positive and negative numbers 
// alternately using Two pointers 
import java.util.*;

class GfG {

    // Function to rearrange positive and negative numbers
    // in alternate fashion
    static void rearrange(ArrayList<Integer> arr) {
        ArrayList<Integer> pos = new ArrayList<>();
        ArrayList<Integer> neg = new ArrayList<>();

        // Separate positive and negative numbers
        for (int i = 0; i < arr.size(); i++) {
            if (arr.get(i) >= 0)
                pos.add(arr.get(i));
            else
                neg.add(arr.get(i));
        }

        int posIdx = 0, negIdx = 0;
        int i = 0;

        // Place positive and negative numbers alternately
        // in the original array
        while (posIdx < pos.size() && negIdx < neg.size()) {
            if (i % 2 == 0)
                arr.set(i++, pos.get(posIdx++));
            else 
                arr.set(i++, neg.get(negIdx++));
        }

        // Append remaining positive numbers (if any)
        while (posIdx < pos.size())
            arr.set(i++, pos.get(posIdx++));

        // Append remaining negative numbers (if any)
        while (negIdx < neg.size())
            arr.set(i++, neg.get(negIdx++));
    }

    public static void main(String[] args) {
        ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(1, 2, 3, -4, -1, 4));
        rearrange(arr);
        for (int i = 0; i < arr.size(); i++) 
            System.out.print(arr.get(i) + " ");
    }
}

Python

# Python program to rearrange positive and negative numbers 
# alternately using Two pointers 

# Function to rearrange positive and negative integers 
# in alternate fashion
def rearrange(arr):
    pos = []
    neg = []

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

    posIdx = 0
    negIdx = 0
    i = 0

    # Place positive and negative numbers alternately
    # in the original array
    while posIdx < len(pos) and negIdx < len(neg):
        if i % 2 == 0:
            arr[i] = pos[posIdx]
            posIdx += 1
        else:
            arr[i] = neg[negIdx]
            negIdx += 1
        i += 1

    # Append remaining positive numbers (if any)
    while posIdx < len(pos):
        arr[i] = pos[posIdx]
        posIdx += 1
        i += 1

    # Append remaining negative numbers (if any)
    while negIdx < len(neg):
        arr[i] = neg[negIdx]
        negIdx += 1
        i += 1

if __name__ == "__main__":
    arr = [1, 2, 3, -4, -1, 4]
    rearrange(arr)
    print(' '.join(map(str, arr)))

// C# program to rearrange positive and negative numbers 
// alternately using Two pointers 

using System;
using System.Collections.Generic;

class GfG {
    
    // Function to rearrange positive and negative numbers
    // in alternate fashion
    static void rearrange(int[] arr) {
        List<int> pos = new List<int>();
        List<int> neg = new List<int>();

        // Separate positive and negative numbers
        for (int i = 0; i < arr.Length; i++) {
            if (arr[i] >= 0)
                pos.Add(arr[i]);
            else
                neg.Add(arr[i]);
        }

        int posIdx = 0, negIdx = 0;
        int arrIdx = 0;

        // Place positive and negative numbers alternately
        // in the original array
        while (posIdx < pos.Count && negIdx < neg.Count) {
            if (arrIdx % 2 == 0)
                arr[arrIdx++] = pos[posIdx++];
            else
                arr[arrIdx++] = neg[negIdx++];
        }

        // Append remaining positive numbers (if any)
        while (posIdx < pos.Count)
            arr[arrIdx++] = pos[posIdx++];

        // Append remaining negative numbers (if any)
        while (negIdx < neg.Count)
            arr[arrIdx++] = neg[negIdx++];
    }

    static void Main() {
        int[] arr = { 1, 2, 3, -4, -1, 4 };
        rearrange(arr);
        for (int i = 0; i < arr.Length; i++)
            Console.Write(arr[i] + " ");
    }
}

JavaScript

// JavaScript program to rearrange positive and negative numbers 
// alternately using Two pointers 

// Function to rearrange positive and negative numbers
// in alternate fashion
function rearrange(arr) {
    let pos = [];
    let neg = [];

    // Separate positive and negative numbers
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] >= 0)
            pos.push(arr[i]);
        else
            neg.push(arr[i]);
    }

    let posIdx = 0, negIdx = 0;
    let i = 0;

    // Place positive and negative numbers alternately
    // in the original array
    while (posIdx < pos.length && negIdx < neg.length) {
        if (i % 2 === 0)
            arr[i++] = pos[posIdx++];
        else 
            arr[i++] = neg[negIdx++];
    }

    // Append remaining positive numbers (if any)
    while (posIdx < pos.length)
        arr[i++] = pos[posIdx++];

    // Append remaining negative numbers (if any)
    while (negIdx < neg.length)
        arr[i++] = neg[negIdx++];
}

// Driver Code
let arr = [1, 2, 3, -4, -1, 4];
rearrange(arr);
console.log(arr.join(' '));

Output

1 -4 2 -1 3 4

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

Rearrange Array by Sign

Explore