Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

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

You may also like...