This post is completed by 1 user

  • 0
 Add to List
Hard

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, and 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 every alternate element in the left half (negative elements) with the elements in the right (positive elements)

Code:


Output:

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

Also Read: