The problem
Reorder an array so nums[0] < nums[1] > nums[2] < nums[3]… (strict inequalities, duplicates allowed).
Stuck? Reveal hints one at a time
How to approach it
- 1Sort the array; find mid = ⌈n/2⌉.
- 2Small half = first mid elements; large half = the rest.
- 3Fill odd indices (1, 3, 5…) with the large half REVERSED; even indices (0, 2, 4…) with the small half REVERSED.
- 4Reversal pushes duplicated boundary values maximally apart, preserving strictness.
Key insight
The danger is duplicates straddling the split (e.g. [4,5,5,6]) — reversing both halves separates equal values by the largest possible index distance.
The solution
Watch out for
- Forgetting the reversal fails on [1,2,2,3]-style inputs where duplicates land adjacent.
- The O(n) median + virtual-index three-way-partition solution exists — mention it as the follow-up.