Rearrange an array such that it contains alternate positive and negative numbers

Problem

You are given an array. Rearrange the elements such that positive and negative integers occur at alternate positions.

Sample Input

[9, -3, 5, -2, -8, -6, 1, 3]

Sample output

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

Explanation

We can make 0 as our pivot element and partition the array into negative elements on the left side of the pivot and positive elements on the right side of the pivot using the approach of the quicksort algorithm.

Later, we can swap alternate negative elements with positive elements until all positive and negative elements are exhausted.

C++

#include<bits/stdc++.h>
usingnamespacestd;
intpartitionHelper(int arr[], int n)
{
 int j = 0;
 int pivot = 0; 
 for (int i = 0; i < n; i++)
 {
 if (arr[i] < pivot)
 {
 swap(arr[i], arr[j]);
 j++;
 }
 }
 return j;
}
intsolve(int arr[], int n)
{
 int p = partitionHelper(arr, n);
 for (int i = 0; (p < n && i < p); p++, i += 2) {
 swap(arr[i], arr[p]);
 }
}
intmain()
{
 int arr[] = {1, 2, -4, -5};
 int n = sizeof(arr)/sizeof(arr[0]);
 solve(arr, n);
 for (int i = 0; i < n; i++) {
 cout << " " << arr[i];
 }
 return0;
}

Output

1 -5 2 -4

C

#include<stdio.h>
voidswap(int *x, int *y)
{
 int temp = *x;
 *x = *y;
 *y = temp;
}
intpartitionHelper(int arr[], int n)
{
 int j = 0;
 int pivot = 0; 
 for (int i = 0; i < n; i++)
 {
 if (arr[i] < pivot)
 {
 swap(&arr[i], &arr[j]);
 j++;
 }
 }
 return j;
}
intsolve(int arr[], int n)
{
 int p = partitionHelper(arr, n);
 for (int i = 0; (p < n && i < p); p++, i += 2) {
 swap(&arr[i], &arr[p]);
 }
}
intmain()
{
 int arr[] = {1, 2, -4, -5};
 int n = sizeof(arr)/sizeof(arr[0]);
 solve(arr, n);
 for (int i = 0; i < n; i++) {
 printf("%d ",arr[i]);
 }
 return0;
}

Output

1 -5 2 -4

Python

defpartitionHelper(arr):
 j = 0
 pivot = 0 
 for i in range(len(arr)):
 if arr[i] < pivot:
 temp = arr[i]
 arr[i] = arr[j]
 arr[j] = temp
 j = j + 1
 return j
defsolve(arr):
 p = partitionHelper(arr)
 n = 0
 while len(arr) > p and p > n:
 temp = arr[n]
 arr[n] = arr[p]
 arr[p] = temp
 p = p + 1
 n = n + 2
arr = [1,2,-5,-4]
solve(arr)
print(arr)

Output

[1, -4, 2, -5]

People are also reading:

• Find all symmetric pairs in an array of pairs
• Print all subarrays of an array having distinct elements
• Find dropping point of an egg
• Nth root of M
• Find MSB
• Longest Substring without repeating characters
• Delete Nodes And Return Forest
• Longest Consecutive Sequence in Linear time
• Sorted Triplet in an Array
• Activity Selection Problem