Wiggle Sort II

Wiggle Sort II looks like a puzzle about positions, but it is a selection problem. You do not need the array sorted. You only need to know which values belong to the small half and which to the large half — and that is exactly what quickselect finds, one element in its final place, in O(n) average time.

It also hides a trap. Duplicates of the middle value can end up side by side, which breaks the strict "less than" rule. The fix is one reversal, and understanding why is the heart of the lesson.

The problem

Rearrange an array in place so that nums[0] < nums[1] > nums[2] < nums[3] > … — each even index is strictly smaller than its neighbours, and each odd index strictly larger. The input is guaranteed to have at least one valid arrangement. Return any one.

• [5, 1, 5, 7, 3, 5] → for example [5, 7, 3, 5, 1, 5]: 5 is less than 7, 7 is more than 3, 3 is less than 5, 5 is more than 1, 1 is less than 5.
• [4, 5, 5, 6] → [5, 6, 4, 5].

Constraints: 1 ≤ n ≤ 5 × 10⁴, values from 0 to 5000.

Clarifying questions

• Strict inequalities? Yes, which is what makes duplicates dangerous. (With ≤ and ≥, one pass of swapping neighbours suffices.)
• Is an answer guaranteed? Yes. [1, 1, 1, 2] would have none, and will not be given.
• Any valid arrangement? Yes.
• In place? Yes; O(n) extra space is acceptable for the main solution.

Approach 1: the simple way

Try every arrangement until one wiggles. With n! orders this is hopeless beyond about 10 elements. A better simple way is to sort, then deal the small half into even slots and the large half into odd slots. Every even slot then holds a value from the small half and every odd slot one from the large half, so each neighbour pair is "small next to large".

Deal them in plain order and it usually works. On [5, 1, 5, 7, 3, 5], sorted is [1, 3, 5, 5, 5, 7], small half [1, 3, 5], large half [5, 5, 7]. Dealing in order gives [1, 5, 3, 5, 5, 7] — and at indices 3 and 4, a 5 sits next to a 5. The middle value appears in both halves, and in plain order its copies meet at the seam.

The fix: deal both halves in reverse. The small half's copies of the middle value go to the first even slots, and the large half's copies go to the last odd slots — as far apart as possible.

1def wiggle_sort_sorted(nums: list[int]) -> None:2    """Sort, then fill even slots and odd slots from the two halves, each reversed."""3    ordered = sorted(nums)4    half = (len(nums) + 1) // 2        # the small half gets the extra element5    nums[::2] = ordered[:half][::-1]   # small values, largest first6    nums[1::2] = ordered[half:][::-1]  # large values, largest first

On the example: small reversed [5, 3, 1], large reversed [7, 5, 5], interleaved [5, 7, 3, 5, 1, 5]. Valid.

This is O(n log n) time and O(n) space. It is correct and it passes. The follow-up is: the sort does more work than needed — can you do it in O(n)?

The key insight

Look at what the dealing step actually used from the sort. Not the full order. Only this: which values go in the small half, and which copies of the middle value sit at the seam. If the array is arranged as

[values below the middle value | copies of the middle value | values above]

then the first half positions are a valid small half, with the middle-value copies at its end, and the rest is a valid large half, with the middle-value copies at its start — exactly where they were in the sorted array. Reversing and dealing works just the same.

Getting that arrangement needs two tools from the core lesson:

1. Quickselect finds the middle value — the one that would sit at index half − 1 after sorting — in O(n) average time.
2. Three-way partition around that value produces "below | equal | above" in one O(n) pass. It is Sort Colors with "below", "equal" and "above" in place of 0, 1 and 2.

Approach 2: optimised — quickselect, partition, interleave

This uses select and partition3 exactly as written in the core lesson.

1def wiggle_sort(nums: list[int]) -> None:2    """Quickselect the middle value, partition around it, then interleave."""3    n = len(nums)4    half = (n + 1) // 2                      # size of the small half5    middle = select(nums[:], half - 1)       # largest value of the small half6    partition3(nums, 0, n - 1, middle)       # [smaller | equal | larger]7    small, large = nums[:half], nums[half:]8    nums[::2] = small[::-1]                  # small values, largest first9    nums[1::2] = large[::-1]                 # large values, largest first

On [5, 1, 5, 7, 3, 5], n = 6 and half = 3. Quickselect returns the value at sorted index 2, which is 5. Then the three-way partition around 5:

The result is [1, 3 | 5, 5, 5 | 7]. Small half [1, 3, 5], large half [5, 5, 7]; reversed and dealt, [5, 7, 3, 5, 1, 5]. Here the partition happened to produce fully sorted order; in general the "below" and "above" blocks stay unordered, and that is fine — only the position of the middle-value block matters.

Complexity: O(n) average time — quickselect is O(n) on average, and the partition and the dealing are O(n) each. O(n) space for the copy passed to select and the two halves. The worst case is O(n²) if quickselect is unlucky, which a random pivot makes very unlikely.

Both versions were checked on 3,000 random arrays: whenever the brute force found a valid arrangement, both produced one, using the same values.

Edge cases

• One element: nothing to compare; half = 1, the array is unchanged.
• Two elements, [1, 2]: small [1], large [2]; result [1, 2].
• Many copies of the middle value, [3, 3, 3, 4, 4, 5]: the reversal keeps the three 3s on even slots 0, 2 and 4, each next to a 4 or a 5.
• Odd length, [1, 1, 2]: the small half gets the extra element; result [1, 2, 1].

Follow-ups

• O(1) extra space? Do the three-way partition directly on "virtual" indices (1 + 2i) % (n | 1), which walk the odd slots first and then the even ones, so no halves are copied. It is the same idea with an index mapping, and a common hard follow-up.
• Non-strict wiggle (≤, ≥)? One pass: at each index, swap with the next element if the pair is in the wrong direction. O(n), no selection needed.
• Just the k-th largest value? That is quickselect alone. The Heaps section compares it with the size-k heap: the heap is O(n log k) and works on a stream; quickselect is O(n) on average and needs the whole array.