Segregate positive and negative integers in linear time
Given an array of positive and negative integers, segregate them in linear time and constant space. The output should print all negative numbers, followed by all positive numbers.
For example,
Output: [-3, -2, -8, -6, 5, 9, 1, 3]
We can solve this problem in linear time by using the partitioning logic of Quicksort. The idea is to use 0 as a pivot element and make one pass of the partition process. The resultant array will satisfy the given constraints. Following is the C++, Java, and Python 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 |
#include <iostream> #include <algorithm> using namespace std; void partition(int a[], int n) { int pIndex = 0; // each time we find a negative number, `pIndex` is incremented, // and that element would be placed before the pivot for (int i = 0; i < n; i++) { if (a[i] < 0) // pivot is 0 { swap(a[i], a[pIndex]); pIndex++; } } } int main() { int a[] = { 9, -3, 5, -2, -8, -6, 1, 3 }; int n = sizeof(a)/sizeof(a[0]); partition(a, n); // 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 35 |
import java.util.Arrays; class Main { public static void partition(int[] a) { int pIndex = 0; // each time we find a negative number, `pIndex` is incremented, // and that element would be placed before the pivot for (int i = 0; i < a.length; 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); System.out.println(Arrays.toString(a)); } } |
Output:
[-3, -2, -8, -6, 5, 9, 1, 3]
Python
|
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 |
def swap(a, i, j): temp = a[i] a[i] = a[j] a[j] = temp def partition(a): pIndex = 0 # each time we find a negative number, `pIndex` is incremented, # and that element would be placed before the pivot for i in range(len(a)): if a[i] < 0: # pivot is 0 swap(a, i, pIndex) pIndex = pIndex + 1 if __name__ == '__main__': a = [9, -3, 5, -2, -8, -6, 1, 3] partition(a) print(a) |
Output:
[-3, -2, -8, -6, 5, 9, 1, 3]
The time complexity of the above solution is O(n) and doesn’t require any extra space, where n is the size of the input.
The problem with this approach is that it changes the relative order of elements. The following solution uses the merge sort algorithm and maintains the relative order of elements.
Exercise: Modify the solution so that positive integers will come first.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)