Given an array of integers, rearrange the array such that it contains positive and negative numbers at alternate positions. If array contains more positive or negative elements, they should be moved to end of the array.

For example,

**Input: **{ 9, -3, 5, -2, -8, -6, 1, 3 }

** Output: **{ 5, -2, 9, -6, 1, -8, 3, -3 }

**Input: **{ 9, -3, 5, -2, -8, -6 }

** Output: **{ 5, -2, 9, -6, -3, -8 }

**Input: **{ 9, -3, 5, -2, 8, 6, 1, 3 }

** Output: **{ 5, -2, 9, -3, 8, 6, 1, 3 }

We can solve this problem in linear time by using partitioning logic of quicksort. The idea is to use 0 as pivot element and make one pass of partition process. The resultant array will contain all positive integers at the end of the array and all negative integers in the beginning. Then we swap alternate negative element from next available positive element till end of array is reached or all negative or positive integers are exhausted.

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
#include <iostream> #include <algorithm> #include <iomanip> using namespace std; // Partitioning routine of quicksort int partition(int A[], int n) { int j = 0; int pivot = 0; // consider 0 as pivot // each time we find a negative number, j is incremented // and negative element would be placed before the pivot for (int i = 0; i < n; i++) { if (A[i] < pivot) { swap(A[i], A[j]); j++; } } // j holds index of first positive element return j; } // Function to rearrange given array such that it contains positive // and negative numbers at alternate positions int rearrange(int A[], int size) { // partition given array such that all positive elements move // to end of the array int p = partition(A, size); // swap alternate negative element from next available positive // element till end of array is reached or all negative or // positive elements are exhausted. for (int n = 0; (p < size && n < p); p++, n += 2) { swap(A[n], A[p]); } } // main function int main() { int A[] = { 9, -3, 5, -2, -8, -6, 1, 3 }; int n = sizeof(A)/sizeof(A[0]); rearrange(A, n); // print the rearranged array for (int i = 0 ; i < n; i++) { cout << setw(3) << A[i]; } return 0; } |

`Output:`

5 -2 9 -6 1 -8 3 -3

The time complexity of above solution is O(n) and auxiliary space used by the program is O(1). The problem with this approach is that it changes relative order of elements.

**Exercise:** Implement a solution that maintains the relative order of elements.

**Thanks for reading.**

Please use our online compiler to post code in comments. To contribute, get in touch with us.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply