Wiggle Sort

How it works

This is an optimized version of the greedy approach using XOR for condition checking. The key observation is that we need to swap when the parity of the index does not match whether the current element is greater than the previous. Using XOR on these two boolean conditions elegantly captures when a swap is needed.

Steps

1. Iterate through the array starting from index 1.
2. For each position, compute two values: whether the index is odd (i % 2) and whether the current element is greater than the previous (nums[i] > nums[i-1]).
3. If the XOR of these two values is true (they differ), swap the current element with the previous one.
4. The array is wiggle sorted after one complete pass.

Complexity

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

Things to watch for

Confusing Wiggle Sort with Wiggle Sort II

Wiggle Sort requires nums[0] <= nums[1] >= nums[2] <= nums[3]... (non-strict inequalities), while Wiggle Sort II requires strict inequalities. Using the wrong condition will fail test cases with duplicate elements.

Swapping with Wrong Neighbor

The greedy approach compares each element with its previous element (i-1), not the next element (i+1). Swapping with the wrong neighbor breaks the already-established wiggle pattern.

Starting Loop at Index 0 Instead of 1

The greedy approach needs to compare each element with its predecessor, so the loop must start at index 1. Starting at 0 causes an index-out-of-bounds error when accessing nums[i - 1].

from typing import List

class Solution:
    def wiggleSort(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """

        for i in range(1, len(nums)):
            if (i % 2) ^ (nums[i] > nums[i - 1]):
                nums[i], nums[i - 1] = nums[i - 1], nums[i]

class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        for (int i = 1; i <nums.size(); i++) {
            if ((i % 2) ^ (nums[i] > nums[i - 1])) {
                swap(nums[i], nums[i - 1]);
            }
        }
    }
};