This post is completed by 2 users

  • 0
 Add to List
Hard

15. Efficiently Rearrange Positive and Negative Numbers in Array on Each Side

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.

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

Example

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

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

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

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

  1. 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')
  2. 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')
  3. 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

Related Problems: