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.

 
Thanks for reading.

Please use our online compiler to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
Notify of