Wiggle Sort

Problem Statement

Reorder nums in place so that nums[0] <= nums[1] >= nums[2] <= nums[3] ... (an alternating "wiggle" pattern). Any valid arrangement is accepted.

Example

Input:  [3, 5, 2, 1, 6, 4]
Output: [3, 5, 1, 6, 2, 4]  (one valid wiggle)

Approach

A single greedy pass suffices. At each index i, the required relation alternates: at even i we want nums[i] <= nums[i+1], at odd i we want nums[i] >= nums[i+1]. Whenever the current pair violates the needed relation, swap them. (Sorting then swapping adjacent pairs also works but is O(n log n).)

Complexity

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

Solution Code

Python

def wiggleSort(nums):
    for i in range(len(nums) - 1):
        if (i % 2 == 0) == (nums[i] > nums[i + 1]):
            nums[i], nums[i + 1] = nums[i + 1], nums[i]
    return nums

Java

void wiggleSort(int[] nums) {
    for (int i = 0; i < nums.length - 1; i++) {
        boolean even = (i % 2 == 0);
        if (even == (nums[i] > nums[i + 1])) {
            int t = nums[i]; nums[i] = nums[i + 1]; nums[i + 1] = t;
        }
    }
}

C++

void wiggleSort(vector<int>& nums) {
    for (int i = 0; i + 1 < (int)nums.size(); i++) {
        bool even = (i % 2 == 0);
        if (even == (nums[i] > nums[i + 1])) swap(nums[i], nums[i + 1]);
    }
}

Key Takeaways

• A greedy one-pass swap achieves the wiggle in O(n), beating sort-based O(n log n).
• The required inequality flips with the parity of the index.
• Reference: LeetCode 280 (Wiggle Sort).