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 Numbers of Array On Each Side in O(nlogn)

Objec­tive: Rearrange Pos­i­tive and Neg­a­tive Num­bers of an Array so that one side you have pos­i­tive num­bers and other side with neg­a­tive Inte­gers with­out chang­ing their respec­tive order.

Example : Input :  1 -2 3 -4 5 -6 7 -8 9 -10

ReArranged Output :  -2 -4 -6 -8 -10 1 3 5 7 9

Input: An array with pos­i­tive and neg­a­tive numbers

Out­put: Mod­i­fied array with pos­i­tive num­bers and neg­a­tive num­bers are on each side of the array.

Approach:

Method 1. One naive approach is to have another array of same size and nav­i­gate the input array and one scan place all the neg­a­tive num­bers to the new array and in sec­ond scan place all the pos­i­tive num­bers to new array. Here the Space com­plex­ity will be O(n). We have a bet­ter solu­tion which can solve this in O(1) space.

Method 2: Divide and Con­quer

  • This approach is sim­i­lar to merge sort.
  • Divide the array into two half, Solve them indi­vid­u­ally and merge them.
  • Tricky part is in merging.

Merg­ing: (Neg­a­tive on left side and pos­i­tives on the right side)

  • Nav­i­gate the left half of array till you won’t find a pos­i­tive inte­ger and reverse the array after that point.(Say that part is called ‘A’)
  • Nav­i­gate the right half of array till you won’t find a pos­i­tive inte­ger and reverse the array before that point. (Say that part is called ‘B’)
  • Now reverse the those parts from both the array (A and B), See exam­ple for bet­ter explanation.
Rearrange Positive and Negative Numbers of Array On Each Side

Rearrange Pos­i­tive and Neg­a­tive Num­bers of Array On Each Side

Com­plete Code:


Out­put:

Input : 1 -2 -3 -4 5 -6 7 -8 9 -10 -11 -12 20
ReArranged Output : -2 -3 -4 -6 -8 -10 -11 -12 1 5 7 9 20

You may also like...

  • Xiheng Yue

    This is very clever! Thank you!