MediumArraysSortingDivide and Conquer

Wiggle Sort II

1 approach, code in every language

Reorder an integer array in place so its values alternate in a strict zig-zag: the element at every odd index must be strictly larger than its neighbors, giving the pattern nums[0] < nums[1] > nums[2] < nums[3] and so on.

The input is guaranteed to permit at least one valid arrangement, and if several are possible any of them is acceptable.

Example 1

Input: nums = [1,5,1,1,6,4]

Output: [1,6,1,5,1,4]

Each peak sits at an odd index and exceeds both neighbors; other valid answers also exist.

Example 2

Input: nums = [1,3,2,2,3,1]

Output: [2,3,1,3,1,2]

Constraints

1 ≤ nums.length ≤ 5 * 10^4
0 ≤ nums[i] ≤ 5000

Sort Then Interleave From the Ends

Sort a copy, then weave the smaller half into the even slots and the larger half into the odd slots, taking each half from its largest element downward.

Loading animation…

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

1Make a sorted copy of the array.
2Decide the split point so the smaller half fills the even indices; it takes the extra element when the length is odd.
3Fill even indices by pulling values from the top of the smaller half downward.
4Fill odd indices by pulling values from the top of the larger half (the overall largest) downward.
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]

Time

O(n log n)

Space

O(n)

Dominated by the sort plus an auxiliary copy of the array.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Arrays

After the pattern

Now solve one you haven't seen.

Laying the Readings Out in a Zigzag is our own problem on the technique behind Wiggle Sort II: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free