Wiggle Sort II: The Median Split Interleave

324. Wiggle Sort II asks you to reorder nums in-place so that nums[0] < nums[1] > nums[2] < nums[3].... Given [1,5,1,1,6,4], a valid answer is [1,6,1,5,1,4]. Every even index is a valley (strictly less than its neighbors), and every odd index is a peak (strictly greater than its neighbors).

This is trickier than the original Wiggle Sort (LeetCode 280), which only requires >= alternation. Loose inequalities are easy to satisfy even when duplicates exist. Strict inequalities mean you have to be careful about where duplicate values land, because two equal adjacent elements immediately violate the constraint.

The approach: sort, split, interleave from the ends

The idea has three parts.

Sort the array. Once sorted, you know exactly where the boundary between smaller and larger values is.

Split at the median. With n elements, set mid = (n - 1) // 2. Everything at indices 0..mid is the smaller half; everything at indices mid+1..n-1 is the larger half. The formula (n - 1) // 2 is the right midpoint for both odd and even lengths. For n=6 it gives mid=2; for n=5 it gives mid=2 as well, leaving a 3-element smaller half and a 2-element larger half.

Interleave from the ends. Place elements from the smaller half into even positions (0, 2, 4, ...) and elements from the larger half into odd positions (1, 3, 5, ...). The key detail is that you read each half from its end rather than its start.

• Fill even positions: start lo = mid, place arr[lo] at nums[0], then arr[lo-1] at nums[2], and so on.
• Fill odd positions: start hi = n - 1, place arr[hi] at nums[1], then arr[hi-1] at nums[3], and so on.

Why from the end? If arr[mid] equals arr[mid+1] (a duplicate straddles the boundary), placing them into the result by reading inward from each half's end keeps those equal elements as far apart as possible. If you read from the start of each half instead, those duplicates would be placed into adjacent positions and break the strict inequality.

def wiggleSort(nums: list[None]) -> None:
    arr = sorted(nums)
    n = len(nums)
    mid = (n - 1) // 2
    lo, hi = mid, n - 1
    for i in range(0, n, 2):
        nums[i] = arr[lo]
        lo -= 1
    for i in range(1, n, 2):
        nums[i] = arr[hi]
        hi -= 1

Complexity

The solution above copies the sorted array, so it uses O(n) extra space. An O(n) time, O(1) space solution exists using nth_element to find the median in linear time, then applying a 3-way partition (similar to Dutch National Flag) to rearrange elements around the median in a virtual index space. It is considerably more complex and rarely asked in interviews.

The building blocks

Sorting as a preprocessing step. Once the array is sorted, the smaller and larger halves are clearly defined and you can fill positions in one linear pass. This is a general trick: sometimes it is better to pay O(n log n) upfront to make the main logic trivial rather than trying to handle an unsorted input cleverly.

Two-pointer interleaving. The lo and hi pointers walk inward from the ends of their respective halves while the write pointer i steps through alternating positions. This is the same two-pointer interleaving pattern used in merge-step of merge sort, just written to a shuffled index sequence instead of a contiguous output.

Why (n-1)//2 is the correct midpoint. For n=6: (6-1)//2 = 2, giving a smaller half of size 3 (arr[0..2]) and a larger half of size 3 (arr[3..5]). For n=5: (5-1)//2 = 2, giving a smaller half of size 3 (arr[0..2]) and a larger half of size 2 (arr[3..4]). The even positions always need at least as many elements as the odd positions because there is one more even index than odd index when n is odd. (n-1)//2 ensures the smaller half is the larger of the two halves when sizes differ, which is exactly what you need.

Edge cases

All same elements. If every value is equal there is no valid wiggle order with strict inequalities. LeetCode's constraints guarantee a valid answer exists, so you will not see this case. But it is good to know why: the algorithm would produce [x, x, x, x, ...] and every adjacent pair would violate the strict inequality.

Two elements. n=2, mid=0. Even positions: nums[0] = arr[0]. Odd positions: nums[1] = arr[1]. Since arr[0] <= arr[1] after sorting and a valid answer is guaranteed, you get nums[0] < nums[1]. Done.

Already wiggled. The algorithm ignores the current order entirely, sorts a copy, and writes fresh values. There is no special case for arrays that are already in wiggle order.

From understanding to recall

After reading this, the overall shape of the solution probably feels clear: sort, split, interleave. What will slip in an interview is the direction of the fill. Your brain will want to write lo = 0 (start of the smaller half) instead of lo = mid (end of the smaller half).

The mnemonic is: fill from the back of each half. The back of the smaller half is index mid; the back of the larger half is index n-1. When you see a wiggle sort problem with strict inequalities, the first thing to lock in is that both pointers start at the far end of their half and count down.

Spaced repetition reps should focus on this single detail. Everything else follows from the structure. Write the solution from scratch, and when you set up lo and hi, say out loud: "back of the smaller half, back of the larger half."

Related posts

• Sort Colors - Dutch National Flag 3-way partition, the pattern behind the O(1) space variant of this problem
• Kth Largest Element - Finding the median in O(n) with quickselect, the key to the optimal solution
• Find the Duplicate Number - Another problem where duplicate elements force you to think carefully about placement