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

Posted in

Last updated on July 21, 2024

## 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;
}

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;
}

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: