# Re-arrange elements in an array to put positive and negative elements in alternate order

Given an array with positive and negative elements in it, re-arrange these elements such that positive and negative elements are placed in alternate order. Positive elements should be placed at even indices and negative elements should be placed at odd indices. The order of same signed elements should remain same. It is not guaranteed that positive and negative elements are equal in number. If there are more number of positive elements then after arranging positive and negative elements in correct order, remaining positive elements should be placed at the end of the array. Same is the case when there are more number of negative elements. No extra space other than auxiliary variables should be used.

For example, if the input array is {-1,3,2,4,5,-6,7,-9} output should be {3,-1,2,-6,4,-9,5,7}. Note how the order of elements 3,2,4,5,7 and of elements -1,-6,-9 is unchanged among themselves. Also the extra positive elements 5 and 7 are placed at the end of the array. In the sub-array which maintains alternate order, positive elements are placed at even indices and negative elements are placed at odd indices.

## Algorithm/Insights

Before looking at the algorithm, let's first define the right-rotate rotation operation on a given array. If the given array is {-1,3,4,5} then the right-rotate operation on this array would result in array {5,-1,3,4}. Here each element except the last element is right-shifted by one position and the last element is placed at the first position.

Now let's look at the algorithm for re-arranging elements. The steps of the algorithm are -
1. Traverse the array from index 0 to last index.
2. If at any 'index', we find that the element a[index] is not at its right position(if positive element is not at even index and vice versa), then we find out the next element say at index 'nextOpposite' which is of opposite sign to a[index]. Once we find this 'nextOpposite' index we do a right-rotate operation on sub-array ['index'  to 'nextOpposite'] including both extremes. The right-rotate operation puts the element a['nextOpposite'] at position 'index' and maintains the order of remaining elements. If we do not find any opposite signed element, then there are extra elements remaining of either positive / negative sign and we break out of the loop since the algorithm is complete.

Let's look at an example to understand this algorithm.
Input: {-1,3,2,4,5,-6,7,-9}
1. array = {-1,3,2,4,5,-6,7,-9}, index = 0: -1 is not at its right position, next element of opposite sign(3) is found at index 1, right-rotate for sub-array{-1,3} is done and modified array is {3,-1,2,4,5,-6,7,-9}
2. array = {3,-1,2,4,5,-6,7,-9}, index = 1: -1 is now placed at its right position.
3. array = {3,-1,2,4,5,-6,7,-9}, index = 2: 2 is also at its right position.
4. array = {3,-1,2,4,5,-6,7,-9}, index = 3: 4 is not at its right position, next opposite signed element(-6) is at index 5. Right-rotate operation is performed on sub-array{4,5,-6} which results in modified array {3,-1,2,-6,4,5,7,-9}
5. array = {3,-1,2,-6,4,5,7,-9}, index = 4: 4 is now placed at its right position.
6. array = {3,-1,2,-6,4,5,7,-9}, index = 5: 5 is not placed at its right position, right-rotation is performed on sub-array {5,7,-9} which results in modified array {3,-1,2,-6,4,-9,5,7}.
7. All remaining elements are at their right positions.

## Code Snippet

```
package com.ideserve.questions.nilesh;

/**
* <b>IDeserve <br>
* Re-arranges positive and negative elements in alternate order. Positive elements at even indices
* and negative elements at odd indices.
* Runs in O(n^2) time.
* @author Nilesh
*/

public class RearrangeElements {
private void rotateSubarrayRightByOneElement(int[] array, int low, int high) {
int lastElement = array[high];

for (int i = high; i > low; i--) {
array[i] = array[i - 1];
}

array[low] = lastElement;
}

private boolean notAtRightPosition(int[] array, int index) {
// even indices should have positive elements in them
if ((index % 2) == 0) {
// if negative element
if ((array[index]) < 0) {
return true;
} else {
return false;
}
} else // odd indices should have negative elements in them
{
if ((array[index]) < 0) {
return false;
} else {
return true;
}

}
}

private int getNextOpposite(int[] array, int index) {
for (int i = index + 1; i < array.length; i++) {
if ((array[i] * array[index]) < 0) {
return i;
}
}

return -1;
}

public void reArrangePositivesNegatives(int[] array) {
for (int i = 0; i < array.length; i++) {
if (notAtRightPosition(array, i)) {
int nextOppositeIndex = getNextOpposite(array, i);
if (nextOppositeIndex != -1) {
rotateSubarrayRightByOneElement(array, i, nextOppositeIndex);
} else // no more opposite signed elements
{
break;
}
}
}
}

public static void main(String[] args) {
RearrangeElements solution = new RearrangeElements();

int[] testArray = { -1, 3, 2, 4, 5, -6, 7, -9 };

solution.reArrangePositivesNegatives(testArray);

for (int i = 0; i < testArray.length; i++) {
System.out.println(testArray[i]);
}
}
}
```

## Order of the Algorithm

Time Complexity is O(n^2)
Space Complexity is O(1)