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