Wiggle Sort II

Intuition

If we sort the values and drop the smaller half into the even indices and the larger half into the odd indices, we almost get a wiggle. The subtlety is duplicates near the median: placing them next to each other can break the strict inequality. Filling each half from its largest element downward pushes equal values as far apart as possible, so median duplicates end up at opposite ends of the array rather than adjacent, guaranteeing the strict zig-zag.

Algorithm walkthrough

1. 1Make a sorted copy of the array.
2. 2Decide the split point so the smaller half fills the even indices; it takes the extra element when the length is odd.
3. 3Fill even indices by pulling values from the top of the smaller half downward.
4. 4Fill odd indices by pulling values from the top of the larger half (the overall largest) downward.
5. 5Writing both halves back-to-front keeps equal middle values apart, preserving the strict wiggle.

Implementation

class Solution:
    def wiggleSort(self, nums: List[int]) -> None:
        arr = sorted(nums)
        n = len(nums)
        mid = (n + 1) // 2
        small = arr[:mid][::-1]
        large = arr[mid:][::-1]
        for i in range(n):
            if i % 2 == 0:
                nums[i] = small[i // 2]
            else:
                nums[i] = large[i // 2]