Rearrange Array: Move Negative Numbers to the Beginning

Given an array ARR consisting of N integers, rearrange the elements such that all negative numbers are located before all positive numbers. The order of elements in each category (negative or positive) does not matter.

Can you achieve this with O(1) auxiliary space?

Input:

The very first line of input contains an integer ‘T’ denoting the number of test cases. The first line of every test case contains an integer ‘N’, the number of elements in the array. The second line of every test case contains ‘N’ space-separated integers which are the elements of the array.

Output:

For each test case, output “Yes” if the rearranged array is correct as per the problem statement, otherwise print “No”. Each test case result is printed on a new line.

Example:

Input: array = [1, 2, -3, 4, -4, -5] Output: [-3, -5, -4, 2, 4, 1] - or any other arrangement where all negative numbers come before positives.

Constraints:

1 ≤ T ≤ 10

1 ≤ N ≤ 5 * 10⁴

-10⁵ ≤ ARR[i] ≤ 10⁵

Time Limit: 1 sec

Note:

No need to print the results yourself, just return the resulting array as per the problem's requirements.

Question

Rearrange Array: Move Negative Numbers to the Beginning

Given an array ARR consisting of N integers, rearrange the elements such that all negative numbers are located before all positive numbers. The order of elements in each category (negative or positive) does not matter.

Can you achieve this with O(1) auxiliary space?

Input:

The very first line of input contains an integer ‘T’ denoting the number of test cases.
The first line of every test case contains an integer ‘N’, the number of elements in the array.
The second line of every test case contains ‘N’ space-separated integers which are the elements of the array.

Output:

For each test case, output “Yes” if the rearranged array is correct as per the problem statement, otherwise print “No”. Each test case result is printed on a new line.

Example:

Input:
array = [1, 2, -3, 4, -4, -5]
Output:
[-3, -5, -4, 2, 4, 1]
- or any other arrangement where all negative numbers come before positives.

Constraints:

1 ≤ T ≤ 10
1 ≤ N ≤ 5 * 10⁴
-10⁵ ≤ ARR[i] ≤ 10⁵
Time Limit: 1 sec

Note:

No need to print the results yourself, just return the resulting array as per the problem's requirements.

Accepted Answer

Yes, this can be achieved by using a two-pointer approach to rearrange the array with negative numbers at the beginning.

Use two pointers, one starting from the beginning and one from the end of the array.
Swap elements at the two pointers if one is negative and the other is positive, and move the pointers accordingly.
Continue this process until the two pointers meet in the middle of the array.
The resulting array will have all negative numbers before positive numbers, with the order within each category not mattering.