Rearrange Positive and Negative Numbers of Array On Each Side in O(nlogn)

Objective: Rearrange Positive and Negative Numbers of an Array so that one side you have positive numbers and other side with negative Integers without changing their respective 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 positive and negative numbers

Output: Modified array with positive numbers and negative numbers are on each side of the array.

Approach:

Method 1. One naive approach is to have another array of same size and navigate the input array and one scan place all the negative numbers to the new array and in second scan place all the positive numbers to new array. Here the Space complexity will be O(n). We have a better solution which can solve this in O(1) space.

Method 2: Divide and Conquer

  • This approach is similar to merge sort.
  • Divide the array into two half, Solve them individually and merge them.
  • Tricky part is in merging.

Merging: (Negative on left side and positives on the right side)

  • Navigate the left half of array till you won’t find a positive integer and reverse the array after that point.(Say that part is called ‘A’)
  • Navigate the right half of array till you won’t find a positive integer 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 example for better explanation.


Complete Code:

Output:

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

__________________________________________________
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.
__________________________________________________

  • Xiheng Yue

    This is very clever! Thank you!

  • Akshaya Ravi

    Why do we need to reverse here?

    • tutorialhorizon

      so that we can keep the order. if we reverse it once , the order of elements will be reversed but if we reverse it twice we will maintain the order as the original one

  • Seetharaman Narayanan

    Please let me know if this is a better approach. We scan the array from left to right, in the very first instance of a negative number(compare it with pivot), we swap it to begining (pos 0) and increment it to 1 for subsequent -ve number findings.I believe this is O(N) time complexity and O(1) space complexity.

    public static void reArrangePositiveAndNegative(int[] input) {
    int i,j, pivot;
    pivot = 0;
    i=-1; //Not found an index yet for a negative number

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

    private static void swap(int[] input,int a, int b) {
    int temp = input[a];
    input[a] = input[b];
    input[b] = temp;
    }

  • Dhaya Mohan

    Great explanation

%d bloggers like this: