6. Move All Negative Elements to One Side

Given an array, rearrange it so all negative numbers appear before all non-negative numbers, preserving the relative order of elements within each group (a stable partition). Print the result.

Input: The first line contains an integer n. The second line contains n space-separated integers, which may include negatives and non-negatives. Output: Print the rearranged array, space-separated on one line, with all negatives before all non-negatives.

1 <= n <= 10^5

The word 'stable' in a partitioning problem is a strong signal that you likely need an auxiliary structure (or a very careful in-place technique) rather than a simple two-pointer swap, which typically reorders elements within each group.

Rearrange a list so all the negative numbers come first, followed by all the non-negative numbers - keeping each group's own internal order unchanged. Brute force: Repeatedly scan for the next misplaced element and swap it into position, similar to a partition step - this can achieve the split in place, but a naive swap-based approach risks disturbing the STABLE (original relative) order the problem specifically requires within each group. Optimised: Since the problem explicitly requires preserving each group's original relative order (a 'stable' partition), collecting each group into its own separate list during a single pass, then concatenating, guarantees stability automatically - trying to do this with in-place swapping alone (without an auxiliary list) typically breaks stability unless done very carefully.

Assign every element a sort key of 0 if it is negative and 1 otherwise, then apply a stable sorting algorithm (such as merge sort) using that key. Because a stable sort never reorders elements that compare equal, all negatives keep their original relative order and end up first, followed by all non-negatives in their original relative order. This is a simpler and more scalable way to reach a stable partition than manually shifting elements one at a time. Time: O(n log n) Space: O(n)

Make a single left-to-right pass over the array, appending each negative number, in the order encountered, to one output list, and each non-negative number, in the order encountered, to a second output list; then write the negatives list followed by the non-negatives list back out. Since each group is filled purely by appending in scan order, relative order within each group is automatically preserved, and every element is touched only once. True O(1)-extra-space stable partitioning isn't achievable with simple swaps alone, so this trades a linear amount of extra space for linear time. Time: O(n) Space: O(n)

Scan the array left to right, and whenever a negative number is found sitting after some non-negative numbers, repeatedly swap it leftward, one adjacent position at a time, past all the non-negatives ahead of it - similar to a single pass of insertion sort. Because only a negative number and the non-negatives directly in front of it are ever swapped, the relative order within each group is preserved, but shifting one negative number all the way to its place can take up to O(n) swaps, and this can happen for many elements. Time: O(n^2) Space: O(1)

1. Walk through the array once, collecting every negative number (in the order you see them) into one list. 2. At the same time, collect every non-negative number (in the order you see them) into a separate list. 3. Join the two lists together: negatives first, then non-negatives.

Time: O(n) - one pass to collect, one pass (implicit) to combine. Space: O(n), for the two temporary lists (negatives and non-negatives) before combining.

n = 1 (trivially already partitioned); an array that is all-negative or all-non-negative (one group is empty); and n = 10^5 (largest size for the stable partition).

Be ready to explain the difference between a STABLE partition (order preserved within each group, usually needing extra space) and an unstable one (order not guaranteed, but achievable in-place with O(1) extra space) - this exact stability requirement is often the deciding factor in which approach is 'correct' for a given problem.