# Rearrange Positive and Negative Numbers of Array On Each Side in O(nlogn)

**Objective:** Rearrange Positive and Negative Numbers of an Array so that one side you have positive numbers and other side with negative Integers without changing their respective order.

Example: Input : 1 -2 3 -4 5 -6 7 -8 9 -10 ReArranged Output : -2 -4 -6 -8 -10 1 3 5 7 9

**Input:** An array with positive and negative numbers

**Output:** Modified array with positive numbers and negative numbers are on each side of the array.

**Approach:**

**Method 1. **One naive approach is to have another array of same size and navigate the input array and one scan place all the negative numbers to the new array and in second scan place all the positive numbers to new array. Here the Space complexity will be O(n). We have a better solution which can solve this in O(1) space.

**Method 2: Divide and Conquer**

- This approach is similar to merge sort.
- Divide the array into two half, Solve them individually and merge them.
- Tricky part is in merging.

**Merging**: (Negative on left side and positives on the right side)

- Navigate the left half of array till you won’t find a positive integer and reverse the array after that point.(Say that part is called ‘A’)
- Navigate the right half of array till you won’t find a positive integer and reverse the array before that point. (Say that part is called ‘B’)
- Now reverse the those parts from both the array (A and B), See example for better explanation.

**Output**:

Input : 1 -2 -3 -4 5 -6 7 -8 9 -10 -11 -12 20 ReArranged Output : -2 -3 -4 -6 -8 -10 -11 -12 1 5 7 9 20

This is very clever! Thank you!

Why do we need to reverse here?

so that we can keep the order. if we reverse it once , the order of elements will be reversed but if we reverse it twice we will maintain the order as the original one

Please let me know if this is a better approach. We scan the array from left to right, in the very first instance of a negative number(compare it with pivot), we swap it to begining (pos 0) and increment it to 1 for subsequent -ve number findings.I believe this is O(N) time complexity and O(1) space complexity.

public static void reArrangePositiveAndNegative(int[] input) {

int i,j, pivot;

pivot = 0;

i=-1; //Not found an index yet for a negative number

for(j=0; j<=input.length-1;j++) {

if(input[j] <= pivot) {

i++;

if(i!=j) swap(input, i, j);

}

}

}

private static void swap(int[] input,int a, int b) {

int temp = input[a];

input[a] = input[b];

input[b] = temp;

}

Great explanation