Rearrange the array such that it contains positive and negative numbers at alternate positions

Given an array of integers, rearrange the array such that it contains positive and negative numbers at alternate positions. If array contains more positive or negative elements, they should be moved to end of the array.


For example,


Input:  { 9, -3, 5, -2, -8, -6, 1, 3 }
Output: { 5, -2, 9, -6, 1, -8, 3, -3 }

Input:  { 9, -3, 5, -2, -8, -6 }
Output: { 5, -2, 9, -6, -3, -8 }

Input:  { 9, -3, 5, -2, 8, 6, 1, 3 }
Output: { 5, -2, 9, -3, 8, 6, 1, 3 }

 

 
We can solve this problem in linear time by using partitioning logic of quicksort. The idea is to use 0 as pivot element and make one pass of partition process. The resultant array will contain all positive integers at the end of the array and all negative integers in the beginning. Then we swap alternate negative element from next available positive element till end of array is reached or all negative or positive integers are exhausted.

 
C++ implementation –
 

Download   Run Code

Output:

5 -2 9 -6 1 -8 3 -3

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(1). The problem with this approach is that it changes relative order of elements.

 
Exercise: Implement a solution that maintains the relative order of elements.

 
1 Star2 Stars3 Stars4 Stars5 Stars (3 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Toma
Guest