Wiggle Sort II [Medium] — Virtual Index Mapping

Problem Statement

Rearrange such that nums[0] < nums[1] > nums[2] < nums[3]...

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

Intuition

Find median via nth_element. Place larger-half elements at odd indices (descending) and smaller-half at even indices (descending) via a virtual index mapping i → (1+2i) % (n|1).

Solutions

C++

void wiggleSort(vector<int>& nums) {
    int n=nums.size();
    auto mid=nums.begin()+n/2;
    nth_element(nums.begin(),mid,nums.end());
    int median=*mid;
    auto vidx=[&](int i){return (1+2*i)%(n|1);};
    int l=0,r=n-1,k=0;
    while(k<=r){
        if(nums[vidx(k)]>median)  swap(nums[vidx(l++)],nums[vidx(k++)]);
        else if(nums[vidx(k)]<median) swap(nums[vidx(r--)],nums[vidx(k)]);
        else k++;
    }
}

Python (simple sort approach)

def wiggleSort(nums: list[int]) -> None:
    s = sorted(nums)
    n = len(nums)
    # Fill even positions from smaller half (desc), odd from larger half (desc)
    mid = (n - 1) // 2
    nums[::2]  = s[:mid+1][::-1]
    nums[1::2] = s[mid+1:][::-1]

Complexity

Time: O(n) with virtual index; O(n log n) with sort
Space: O(1) in-place