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

Objective: Given an array arrA[] which has negative and positive elements, rearrange the array in such a manner that positive and negative elements occupy the alternate positions and if there are extra positive or negative elements are left then append it to the end.

Examples:

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 Solution: Take the extra space of O(n), do the linear scan twice and fill the positive and negative elements at alternate positions.

But the problem becomes interesting when you have asked not to use any extra space, ask to solve in O(1).

Better Solution : Time Complexity : O(n) Space Complexity: O(1)

Use Quick sort technique.

  • Take the pivot element as 0 and do the first round of Quick Sort.
  • After above step you will have all the negative elements on left and all the positive elements on the right.

  • Then just the every alternate element in the left half (negative elements) with the elements in the right (positive elements)

Complete Code:

Output:

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

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

You may also like...

%d bloggers like this: