# Rearrange Positive and Negative Elements at Alternate Positions in an Array In O(1) Extra Space

Objec­tive: Given an array arrA[] which has neg­a­tive and pos­i­tive ele­ments, rearrange the array in such a man­ner that pos­i­tive and neg­a­tive ele­ments occupy the alter­nate posi­tions and if there are extra pos­i­tive or neg­a­tive ele­ments are left then append it to the end.

Exam­ples:

```int[] arrA = { 1, 2, -3, -4, -5, 6, -7, -8, 9, 10, -11, -12, -13, 14 };
Output: -13 9 -3 10 -5 6 -7 2 -12 1 -11 14 -4 -8
```

Naive Solu­tion: Take the extra space of O(n), do the lin­ear scan twice and fill the pos­i­tive and neg­a­tive ele­ments at alter­nate positions.

But the prob­lem becomes inter­est­ing when you have asked not to use any extra space, ask to solve in O(1).

Bet­ter Solu­tion : Time Com­plex­ity : O(n) Space Com­plex­ity: O(1)

Use Quick sort technique.

• Take the pivot ele­ment as 0 and do the first round of Quick Sort.
• After above step you will have all the neg­a­tive ele­ments on left and all the pos­i­tive ele­ments on the right.

• Then just the every alter­nate ele­ment in the left half (neg­a­tive ele­ments) with the ele­ments in the right (pos­i­tive elements)

Com­plete Code:

Out­put:

```-13 9 -3 10 -5 6 -7 2 -12 1 -11 14 -4 -8
```