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!

  • Akshaya Ravi

    Why do we need to reverse here?

  • Seethara­man Narayanan

    Please let me know if this is a bet­ter approach. We scan the array from left to right, in the very first instance of a neg­a­tive number(compare it with pivot), we swap it to begin­ing (pos 0) and incre­ment it to 1 for sub­se­quent –ve num­ber findings.I believe this is O(N) time com­plex­ity and O(1) space complexity.

    pub­lic sta­tic void reArrangePositiveAndNegative(int[] input) {
    int i,j, pivot;
    pivot = 0;
    i=-1; //Not found an index yet for a neg­a­tive number

    for(j=0; j<=input.length-1;j++) {
    if(input[j] <= pivot) {
    i++;
    if(i!=j) swap(input, i, j);
    }
    }
    }

    pri­vate sta­tic void swap(int[] input,int a, int b) {
    int temp = input[a];
    input[a] = input[b];
    input[b] = temp;
    }