Wiggle Sort II
mediumTime: O(n log n)Space: O(n)
Recognize the pattern
rearrange so nums[0] < nums[1] > nums[2] < nums[3]...alternating peaks and valleys
Brute force idea
Sort and interleave halves — works but doesn't handle duplicates well.
Better approach
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.
Key invariant
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.
Watch out for
Equal elements adjacent — if the median appears many times, naive placement creates adjacent duplicates. Virtual indexing interleaves them correctly.