Rearrange an array such that it contains alternate positive and negative numbers
Given an integer array, rearrange it such that it contains positive and negative numbers at alternate positions. If the array contains more positive or negative elements, move them to the end of the array. Assume that all values in the array are non-zero.
For example,
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 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 contain all positive integers to the end of the array and all negative integers at the beginning. Then swap alternate negative elements from the next available positive element until the end of the array is reached, or all negative or positive integers are exhausted.
Following is the implementation of the above approach in C++, Java, and Python:
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 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 a pivot // each time we find a negative number, `j` is incremented, // and a 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 the index of the first positive element return j; } // Function to rearrange a given array such that it contains positive // and negative numbers at alternate positions int rearrange(int A[], int size) { // partition a given array such that all positive elements move // to the end of the array int p = partition(A, size); // swap alternate negative elements from the next available positive // element till the end of the 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]); } } 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
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 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
import java.util.Arrays; class Main { // Partitioning routine of Quicksort public static int partition(int[] A) { int j = 0; int pivot = 0; // consider 0 as a pivot // each time we find a negative number, `j` is incremented, // and a negative element would be placed before the pivot for (int i = 0; i < A.length; i++) { if (A[i] < pivot) { // swap `A[i]` with `A[j]` int temp = A[i]; A[i] = A[j]; A[j] = temp; j++; } } // `j` holds the index of the first positive element return j; } // Function to rearrange a given array such that it contains positive // and negative numbers at alternate positions public static void rearrange(int[] A) { // partition a given array such that all positive elements move // to the end of the array int p = partition(A); // swap alternate negative elements from the next available positive // element till the end of the array is reached, or all negative or // positive elements are exhausted. for (int n = 0; (p < A.length && n < p); p++, n += 2) { // swap `A[n]` with `A[p]` int temp = A[n]; A[n] = A[p]; A[p] = temp; } } public static void main(String[] args) { int[] A = { 9, -3, 5, -2, -8, -6, 1, 3 }; rearrange(A); // print the rearranged array System.out.println(Arrays.toString(A)); } } |
Output:
[5, -2, 9, -6, 1, -8, 3, -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 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 |
# Partitioning routine of Quicksort def partition(A): j = 0 pivot = 0 # consider 0 as a pivot # each time we find a negative number, `j` is incremented, # and a negative element would be placed before the pivot for i in range(len(A)): if A[i] < pivot: # swap `A[i]` with `A[j]` temp = A[i] A[i] = A[j] A[j] = temp j = j + 1 # `j` holds the index of the first positive element return j # Function to rearrange a given list such that it contains positive # and negative numbers at alternate positions def rearrange(A): # partition a given list such that all positive elements move # to the end of the list p = partition(A) # swap alternate negative elements from the next available positive # element till the end of the list is reached or all negative or # positive elements are exhausted. n = 0 while len(A) > p > n: # swap `A[n]` with `A[p]` temp = A[n] A[n] = A[p] A[p] = temp p = p + 1 n = n + 2 if __name__ == '__main__': A = [9, -3, 5, -2, -8, -6, 1, 3] rearrange(A) print(A) # print the rearranged list |
Output:
[5, -2, 9, -6, 1, -8, 3, -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.
Exercise: Implement a solution that preserves the relative order of elements.
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 :)