Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Last Updated: 13 Nov, 2020

Easy

```
The number of positive integers and negative integers may not be equal. In such cases, add the extra integers at the end.
```

```
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}
```

```
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.
```

```
For each test case, the output is “Valid” if the rearrangement is valid otherwise, “Invalid”, without quotes.
```

```
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.
```

```
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
```

- 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.

All we need to do is store the positive integers and negative integers separately and update the array as asked in the question, the following can be done by:-

- Maintain a list of positives that store all the positive integers from the array.
- Maintain another list of negatives which store all the negative integers from the array.
- Update the array alternatively.

- The idea is to use 0 as the pivot element and apply the partition algorithm of quick sort to the whole array.
- Now, as we know the separating index, all we need to do is arrange the array, the way we want.

partition(arr, size):

- Initialize I and J with 0.
- While J < size:
- If arr[I] < 0: swap arr[J] and arr[I], increment I with 1.
- Increment J with 1.

- While J < size:
- Return I, this is the index where the left side contains all negatives.

rearrange(arr , size):

- positive = partition(arr, size), the index of the first positive integer.
- Update negative with 1, keeping negative integer index 0 and starting first positive integer from index 1.
- Condition 1: positive and negative are in range.
- Condition 2: negative is less than positive.
- Condition 3: negative index contains a negative integer only, if not, this means we have arranged all the negative integers.
- while(all the above conditions satisfy):
- Swap (positive index element with negative index)
- Increment negative by 2.
- Increment positive by 1.

Similar problems

Merge Two Sorted Arrays Without Extra Space

Moderate

Posted: 19 Nov, 2022

Merge Two Sorted Arrays Without Extra Space

Moderate

Posted: 19 Nov, 2022

Ninja And The Strictly Increasing Array

Moderate

Posted: 27 Nov, 2022

Negative To The End

Easy

Posted: 16 Dec, 2022

Sort 0s, 1s, 2s

Easy

Posted: 24 Dec, 2022

Find Duplicate in Array

Easy

Posted: 5 Jun, 2023