Given an array consisting of positive and negative integers, segregate them in linear time and constant space. Output should print contain all negative numbers followed by all positive numbers.

For example,

**Input: **[9, -3, 5, -2, -8, -6, 1, 3]

**Output: **[-3, -2, -8, -6, 5, 9, 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 satisfy the given constraints.

Here’s a C++ and Java program that demonstrates it:

## C++

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 |
#include <iostream> #include <algorithm> using namespace std; void partition(int a[], int start, int end) { int pIndex = start; // each time we find a negative number, pIndex is // incremented and that element would be placed before // the pivot for (int i = start; i <= end; i++) { if (a[i] < 0) // pivot is 0 { swap(a[i], a[pIndex]); pIndex++; } } } // main function int main() { int a[] = { 9, -3, 5, -2, -8, -6, 1, 3 }; int n = sizeof(a)/sizeof(a[0]); partition(a, 0, n - 1); // print the rearranged array for (int i = 0 ; i < n; i++) cout << a[i] << " "; return 0; } |

`Output:`

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

## Java

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 |
import java.util.Arrays; class Partition { public static void partition(int[] a, int start, int end) { int pIndex = start; // each time we find a negative number, pIndex is incremented // and that element would be placed before the pivot for (int i = start; i <= end; i++) { if (a[i] < 0) // pivot is 0 { swap(a, i, pIndex); pIndex++; } } } private static void swap(int[] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } public static void main(String[] args) { int[] a = { 9, -3, 5, -2, -8, -6, 1, 3 }; partition(a, 0, a.length - 1); System.out.println(Arrays.toString(a)); } } |

`Output:`

[-3, -2, -8, -6, 5, 9, 1, 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. We can also modify Merge Sort `merge()` function to solve this problem. The idea is while merging the left- and right- subarray, to merge in such a way that negative elements of both left- and right- subarrays are copied first followed by positive elements of left- and right- subarrays. Note that as left- and right-subarray are already sorted, negative numbers are present in beginning of both subarrays. The time complexity of this solution would be `O(nlogn)` and it maintains the relative order of elements.

**Exercise:** Modify the solution so that positive numbers will come first.

**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