|
This post is completed by 1 user
|
Add to List |
88. Rearrange Array: Positive and Negative Elements Alternating
Objective: Given an array arrA[] containing both negative and positive elements, the task is to rearrange the array such that positive and negative elements occupy alternate positions. If there are extra positive or negative elements remaining, they should be appended to the end of the array.
Examples:
int[] arrA = { 1, 2, -3, -4, -5, 6, -7, -8, 9, 10, -11, -12, -13, 14 };
Output: -13 9 -3 10 -5 6 -7 2 -12 1 -11 14 -4 -8
Naive Solution: Take the extra space of O(n), do the linear scan twice, and fill the positive and negative elements at alternate positions.
But the problem becomes interesting when you have asked not to use any extra space, and ask to solve in O(1).
Better Solution : Time Complexity : O(n) Space Complexity: O(1)
Use the Quick sort technique. - (Click here to read about Quick Sort)
- Take the pivot element as 0 and do the first round of Quick Sort.
- After the above step, you will have all the negative elements on the left and all the positive elements on the right.
- Then swap every alternate element in the left half (negative elements) with the elements in the right (positive elements)
Output:
-13 9 -3 10 -5 6 -7 2 -12 1 -11 14 -4 -8