Move All Negative Numbers to the Beginning

Problem Rearrange an integer array so all negatives precede all non-negatives. Ask the deciding question first: must relative ORDER within each group be preserved?

Input / Output

• Input: int array. Output: rearranged array (in place).

Constraints

• n up to 10^6; O(n) time; O(1) space if order need not be preserved — order preservation changes the problem.

Example

• [1,-2,3,-4,5] → order-free: [-4,-2,3,1,5] (any grouping); stable: [-2,-4,1,3,5].

Expected approach

• Order-free: partition scan (Lomuto-style) — write pointer for negatives, swap each negative encountered to the front region; single pass O(n)/O(1).
• Stable with O(n) space: two lists concatenated. Stable in-place O(1) space is NOT achievable in O(n) with swaps alone — it needs rotation-based block merging (O(n log n)) or insertion shifts (O(n^2)); knowing this boundary is the senior signal. Related: Dutch flag (3-way), move zeroes (same skeleton, stability required).