Alternate Positive and Negative

Easy
0/40
Average time to solve is 15m
profile
Contributed by
44 upvotes
Asked in companies
PayUAmazonDisney + Hotstar

Problem statement

You are given an array ‘arr’ that contains an equal number of positive and negative elements. Rearrange the given array such that positive and negative numbers are arranged alternatively. Also, the respective relative order of positive and negative should be maintained.

For example:

For the given arr[ ] = { -1, 3, 5, 0, -2, -5 } 
arr[ ] = {3, -1, 5, -2, 0, -5 } is valid rearrangement.
arr[ ] = {3, -1, 0, -2, 5, -5 } is invalid rearrangement; order of 0 and 5 is changed. 
arr[ ] = {3, -1, 5, 0, -2, -5 } is invalid rearrangement; positive and negative elements are not alternative.

Note:

Make changes in the same array and no returning or printing is needed.
Consider zero(0) as a positive element for this question.
It is guaranteed that an answer always exists.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer ‘T’, denoting the number of test cases. Then each test case follows.

The first line of each test case contains the Integer ‘N’ denoting the number of elements in the array.

The second and the last line of each test case contains ‘N’ single space-separated integers representing the elements of the array.
Output Format: 
For each test case, print a single line containing ‘N’ single space-separated integers such that positive and negative numbers are arranged alternatively.

Output of each test case will be printed on a separate line.
Note: 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 5
1 <= N <= 5 * 10 ^ 3
-10 ^ 9 <= arr[i] <= 10 ^ 9

Time Limit: 1 sec.
Sample Input 1:
2
6
1 2 3 -1 -2 -3
8
1 -10 5 -1 2 -3 0 -2
Sample Output 1:
1 -1 2 -2 3 -3 
1 -10 5 -1 2 -3 0 -2
Explanation of Sample Input 1:
In the first test case, the output is an array of alternative positive and negative numbers, and also order is maintained (relative order of positive numbers are 1 -> 2 -> 3 and for negative numbers are -1 -> 2 -> -3 )

In the first test case, it is already in valid arrangement.
Sample Input 2:
1
4
-1 0 0 -1
Sample Output 2:
0 -1 0 -1
Explanation of Sample Output 2:
In the first test case, the output is an array of alternative positive and negative numbers and also order is maintained.
Hint

Put one by one element at its correct position.

Approaches (2)
Brute Force

The idea is to rearrange the elements at their correct position one by one from left to right.

 

  • Find the first element which is not at its correct position.
    • A positive number is not at its correct position if it occurs at odd indexes.
    • Similarly, a negative number is not at its correct position, if it occurs at even indexes.
  • Then find the first element after it with the opposite sign.
  • Rotate the subarray between the above two positions (inclusive)

 

Algorithm :

 

  • Take a counter say ‘i’, run a loop from 0 to ‘N’ ( number of elements in a given array ).
  • For each index ‘i’, check
    • If the array element is positive and ‘i’ is odd then
      • find the first element index, let's say ‘idx’ after ‘i’ with the negative sign.
      • Now right rotate the subarray from index ‘i’ to ‘idx’ by 1.
      • increment ‘i’ by 1.
    • If the array element is negative and ‘i’ is even then
      • find the first element index, let's say ‘idx’ after ‘i’ with the positive sign.
      • Now rotate the subarray from index ‘i’ to ‘idx’ by 1.
      • increment ‘i’ by 1.
Time Complexity

O(N ^ 2)   where ‘N’ is the number of elements in a given array.

 

In the worst case, every 2nd element is not at its correct position, then for each we need to calculate the next element with opposite sign that takes O( ‘N’ ) and rotate the subarray takes O( ‘N’ ), So overall time complexity is O(N ) * O( 2 * N ) = O( N ^ 2 ).

 

Space Complexity

O(1)

 

We are rearranging the elements in place, not using any extra space.

 

Code Solution
(100% EXP penalty)
Alternate Positive and Negative
Full screen
Console