Given an array arr[] of length n, containing positive and negative numbers.
The task is to arrange the numbers in an alternate fashion such that every positive number is followed by a negative and vice-versa, maintaining the order of appearance.
The number of positive and negative numbers need not be equal.
If there are more positive numbers, they appear at the end of the array.
If there are more negative numbers, they too appear at the end of the array.
Input: arr[] = {-5, -2, 5, 2, 4, 7, 1, 8, 0, -8}, n=10
Output: -5,5,-2,2,-8,4,7,1,8,0
Input: arr[] = {-4,1,-1,2,3,4}, n=6
Output: -4,1,-1,2,3,4
Solutions
Method 1: In O(n) time and O(n) space
In this approach, we use an auxiliary array, tmp[] and iterate the input array twice.
In the first iteration, store all negatives at the start of tmp[] and all positives at the end of tmp[].
In the second iteration, keep track of -ve and +ve elements in the tmp[] array and fill alternatively in the original array arr[].
Complexity
The time complexity of this solution is O(n) and space complexity is O(n).
Method 2: In O(n^2) time and O(1) space
In this approach, we iterate the array and keep track of the wrongIndex (-ve in the odd index and +ve in the even index).
If the wrongIndex is greater than -1, we attempt to find the next opposite sign element to the one present on the incorrect index.
Once the opposite sign element is found, we rotate the array from "wrongIndex" to "i".
Also, if the difference between "wrongIndex" and "i" is greater than two, we assign wrongIndex = wrongIndex+2 (more than one wrongIndex is skipped), and if not, wrongIndex = -1.
Complexity
The time complexity of this solution is O(n^2) and space complexity is O(1).