Last Updated: 27 Nov, 2020

Alternate Positive and Negative

Easy

Asked in companies

Solve now

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.

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.

Solve now

Approaches

01 Approach

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.

Solve now

02 Approach

The idea is to use two pointers one for the positive numbers and one for the negative number and a temp array. we can iterate the given array and if the current element is positive then we can add this number in 'temp' array at the positive pointer, and vice versa.

Algorithm :

Let’s take a temporary array say ‘temp’ of size ‘N’, a pointer ‘pos’ pointing to positive elements index (even index), initialize it to 0 and a pointer ‘neg’ pointing to negative elements index (odd index) initialize it to 1.
Run a loop from 0 to ‘N’ and for each element check
- If the element is positive or zero.
  - then store the current element at position ‘pos’ in the ‘temp’ array.
  - increment ‘pos’ by 2.
- Else
  - store the current element at position ‘neg’ in the ‘temp’ array.
  - increment ‘neg’ by 2.
Take a counter ‘i’, and run a loop from 0 to ‘N,
- Store the value of ’temp’ at index’ to ‘arr’ at index ‘i’ i.e do arr[i] = temp[i].

Solve now