Wiggle Sort II

Problem Statement

Reorder nums so that nums[0] < nums[1] > nums[2] < nums[3] ... with strict inequalities. Duplicates make this harder than Wiggle Sort I.

Example

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

Approach

Sort the array, then split into a smaller half and a larger half. Place the smaller half into the even indices and the larger half into the odd indices, each filled in reverse. Reversing separates equal values (e.g. medians) so they never land next to each other.

Complexity

• Time: O(n log n)
• Space: O(n)

Solution Code

Python

def wiggleSort(nums):
    nums.sort()
    n = len(nums)
    half = (n + 1) // 2
    small = nums[:half][::-1]
    large = nums[half:][::-1]
    nums[0::2] = small
    nums[1::2] = large

Java

void wiggleSort(int[] nums) {
    int n = nums.length;
    int[] sorted = nums.clone();
    Arrays.sort(sorted);
    int half = (n + 1) / 2, j = half - 1, k = n - 1;
    for (int i = 0; i < n; i++) {
        if (i % 2 == 0) nums[i] = sorted[j--];   // smaller half, reversed
        else nums[i] = sorted[k--];              // larger half, reversed
    }
}

C++

void wiggleSort(vector<int>& nums) {
    int n = nums.size();
    vector<int> sorted(nums);
    sort(sorted.begin(), sorted.end());
    int half = (n + 1) / 2, j = half - 1, k = n - 1;
    for (int i = 0; i < n; i++) {
        if (i % 2 == 0) nums[i] = sorted[j--];
        else nums[i] = sorted[k--];
    }
}

Key Takeaways

• Filling halves in reverse keeps equal median values apart.
• An O(n) solution exists using median-of-medians plus 3-way partition with index mapping.
• Reference: LeetCode 324 (Wiggle Sort II).