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