Rearrange Alternatively

Easy
0/40
Average time to solve is 15m
56 upvotes
Asked in companies
Paytm (One97 Communications Limited)IBMAccenture

Problem statement

Given an array arr of size N containing positive and negative integers. Arrange the array alternatively such that every non-negative integer is followed by a negative integer and vice-versa.

Note:
The number of positive integers and negative integers may not be equal. In such cases, add the extra integers at the end.
For Example:
For array {4, -9, -2, 6, -8}, the output will be {-9, 4, -2, 6, -8}

For array {1, 2, 3, -5}, the output will be {-5, 1, 2, 3}   
Detailed explanation ( Input/output format, Notes, Images )
Input format:
The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then, the T test cases follow.

The first line of each test case or query contains an integer 'N' representing the size of the array (arr).

The second line contains 'N' single space-separated integers, representing the elements in the array.
Output format:
For each test case, the output is “Valid” if the rearrangement is valid otherwise, “Invalid”, without quotes.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

For a single array, multiple solutions may be possible, just rearrange the array in any one possible way.  
Constraints:
1 <= T <= 10 
1 <= N <= 10^5
Sum of N over all test cases does not exceeds 10^5. 
-(10^9) <= arr[i] <= (10^9) 

Time limit: 1 second
Sample input 1:
1
4
-1 2 2 -5 
Sample output 1:
-1 2 -5 2 
Sample input 2:
2
5
-2 -3 -3 -6 -2
3
1 -1 -1
Sample output 2:
-2 -3 -3 -6 -2
-1 1 -1
Hint

Though the question focuses on positives and negatives, we can make our own index condition i.e. let’s say, negatives at even indices and positives at odd indices. Now, we need to find a way to process the array linearly and maintain the index condition, where not satisfied.  

Approaches (3)
Brute force
  • First off, think of your own condition according to which you want to rearrange the array. Let’s say negatives at even indices and positives at odd indices.
  • Now, traverse the given array from start to end:
    Once the condition fails i.e. we find a wrong positioned element, say wrongPositioned:

    We check for the next element having an opposite sign to the wrongPositioned element, say, correct.

    For example: In the case of array [ -2, -3, -4, -5, 6, 8 ] and above told condition (Point 1), the integer ‘-3’ is at the wrong position. Thus, we search for the first element after ‘-3’ with an opposite sign. In the case of this example, that element is ‘6’. 

    Now, we right shift the subarray from wrongPositioned to correct (both inclusive) and place the correct element at the place of wrongPositioned element. 

    In the case of the above example, we right shift the subarray [ -3, -4, -5, 6 ] and update -3 with 6. This makes the array [ -2, 6, -3, -4, -5, 8 ].
     
  • Note: 
    Initial array (A) = [ -2, -3, -4, -5, 6, 8 ]
    Updated array = [ -2, 6, -3, -4, -5, 8 ]
    wrongPositioned = -3 = A[ 1 ]
    Correct = 6 = A[ 4 ]

    When we perform the steps told in the above point, we satisfy condition property for 2 indices:
    -> A[ 1 ] becomes 6, odd index and a positive integer.
    -> A[ 2 ] becomes -3 even index and negative integer.
Time Complexity

O(N ^ 2) per test case where N is the size of the array. 

 

In the worst case, we may traverse N elements N number of times making it N^2. This will be the case when all positive integers are on one side of the array and negative integers are on the other side, for example, [1,0,3,2,-1,-5,-3,4].

Space Complexity

O(1) per test case, 

 

In the worst case, constant extra space is used.

Code Solution
(100% EXP penalty)
Rearrange Alternatively
Full screen
Console