Problem Statement
Wiggle Sort II
You are given an array of numbers. Your job is to rearrange them into a zigzag, also called a wiggle. That means: the first number is smaller than the second, the second is bigger than the third, the third is smaller than the fourth, and so on, up and down the whole way. In symbols, nums[0] nums[2] < nums[3], and the pattern keeps going. The plan is simple to picture. First we line up all the numbers from smallest to largest (sorting). Then we cut the line in half: a smaller half and a larger half. We weave the two halves together so a small number always sits next to a big number. There is one twist. Before weaving, we flip each half so it reads back to front. Flipping matters when there are repeated numbers near the middle. Flipping pushes those equal numbers as far apart as possible, so two equal numbers never end up side by side.
Signals to notice
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.
Trace it on nums=[1,5,1,1,6,4]
sort nums -> sorted=[1,1,1,4,5,6], n=6 mid=(6+1)//2=3 -> split smaller/larger halves small=sorted[:3][::-1]=[1,1,1] (reversed) large=sorted[3:][::-1]=[6,5,4] (reversed) place small at even idx: nums[0]=1, nums[2]=1, nums[4]=1 place large at odd idx: nums[1]=6, nums[3]=5, nums[5]=4 return [1,6,1,5,1,4] -> 1<6>1<5>1<4 valid wiggle
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.
Shape of the loop
sorted = sort(nums) mid = (n + 1) // 2 small = reverse(sorted[:mid]); large = reverse(sorted[mid:]) for i in range(len(small)): nums[2*i] = small[i] # valleys for i in range(len(large)): nums[2*i+1] = large[i] # peaks
Pseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Equal elements adjacent — if the median appears many times, naive placement creates adjacent duplicates. Virtual indexing interleaves them correctly.