Wiggle Sort II
mediumTime: O(n log n)Space: O(n)
Signals to notice
rearrange so nums[0] < nums[1] > nums[2] < nums[3]...alternating peaks and valleys
Brute force first
Sort and interleave halves — works but doesn't handle duplicates well.
The key insight
Find median with quickselect. Three-way partition around median using virtual index mapping. Elements > median at odd indices, < median at even indices. O(n) average.
What must stay true
Elements larger than median go to odd positions (peaks), smaller to even positions (valleys). The median itself fills remaining spots. Virtual indexing ensures no adjacent equal elements.
Easy way to go wrong
Equal elements adjacent — if the median appears many times, naive placement creates adjacent duplicates. Virtual indexing interleaves them correctly.