280. Wiggle Sort - Explanation

Description

Given an integer array nums, reorder it such that nums[0] <= nums[1] >= nums[2] <= nums[3]....

You may assume the input array always has a valid answer.

Example 1:

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

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

Explanation: [1,6,2,5,3,4] is also accepted.

Example 2:

Input: nums = [6,6,5,6,3,8]

Output: [6,6,5,6,3,8]

Constraints:

1 <= nums.length <= 5 * 10^4
0 <= nums[i] <= 10^4
It is guaranteed that there will be an answer for the given input nums.

Follow Up: Could you solve the problem in O(n) time complexity?

Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Sorting - One approach sorts the array first, then swaps adjacent pairs to create the wiggle pattern
Heap / Priority Queue - Max-heap can extract elements in descending order to fill odd indices first
Greedy Algorithms - The optimal O(n) solution uses a single-pass greedy approach, swapping neighbors when the wiggle property is violated

1. Max-Heap

Intuition

For a wiggle sorted array, odd indices should hold larger values and even indices should hold smaller values relative to their neighbors. Using a max-heap, we can extract elements in descending order and strategically place the largest values at odd indices first, then fill even indices with the remaining values. This ensures the wiggle property is maintained.

Algorithm

Push all elements from the array into a max-heap.
First pass: iterate through odd indices (1, 3, 5, ...) and pop from the heap to assign values. These positions get the larger elements.
Second pass: iterate through even indices (0, 2, 4, ...) and pop remaining elements from the heap.
The array is now wiggle sorted in place.

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

        maxHeap = []
        for num in nums:
            heapq.heappush(maxHeap, -num)

        n = len(nums)
        for i in range(1, n, 2):
            nums[i] = -heapq.heappop(maxHeap)
        for i in range(0, n, 2):
            nums[i] = -heapq.heappop(maxHeap)

public class Solution {
    public void wiggleSort(int[] nums) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        for (int num : nums) {
            maxHeap.add(num);
        }

        for (int i = 1; i < nums.length; i += 2) {
            nums[i] = maxHeap.poll();
        }
        for (int i = 0; i < nums.length; i += 2) {
            nums[i] = maxHeap.poll();
        }
    }
}

class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        priority_queue<int> maxHeap;
        for (int& num : nums) {
            maxHeap.push(num);
        }

        for (int i = 1; i < nums.size(); i += 2) {
            nums[i] = maxHeap.top();
            maxHeap.pop();
        }
        for (int i = 0; i < nums.size(); i += 2) {
            nums[i] = maxHeap.top();
            maxHeap.pop();
        }
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @return {void} Do not return anything, modify nums in-place instead.
     */
    wiggleSort(nums) {
        const maxHeap = new PriorityQueue((a, b) => b - a);
        nums.forEach((num) => maxHeap.enqueue(num));

        for (let i = 1; i < nums.length; i += 2) {
            nums[i] = maxHeap.dequeue();
        }
        for (let i = 0; i < nums.length; i += 2) {
            nums[i] = maxHeap.dequeue();
        }
    }
}

public class Solution {
    public void WiggleSort(int[] nums) {
        var maxHeap = new PriorityQueue<int, int>();
        foreach (int num in nums) {
            maxHeap.Enqueue(num, -num);
        }

        for (int i = 1; i < nums.Length; i += 2) {
            nums[i] = maxHeap.Dequeue();
        }
        for (int i = 0; i < nums.Length; i += 2) {
            nums[i] = maxHeap.Dequeue();
        }
    }
}

func wiggleSort(nums []int) {
    maxHeap := &MaxHeap{}
    heap.Init(maxHeap)
    for _, num := range nums {
        heap.Push(maxHeap, num)
    }

    for i := 1; i < len(nums); i += 2 {
        nums[i] = heap.Pop(maxHeap).(int)
    }
    for i := 0; i < len(nums); i += 2 {
        nums[i] = heap.Pop(maxHeap).(int)
    }
}

type MaxHeap []int

func (h MaxHeap) Len() int           { return len(h) }
func (h MaxHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h MaxHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x any)        { *h = append(*h, x.(int)) }
func (h *MaxHeap) Pop() any {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

class Solution {
    fun wiggleSort(nums: IntArray) {
        val maxHeap = PriorityQueue<Int>(Collections.reverseOrder())
        for (num in nums) {
            maxHeap.add(num)
        }

        var i = 1
        while (i < nums.size) {
            nums[i] = maxHeap.poll()
            i += 2
        }
        i = 0
        while (i < nums.size) {
            nums[i] = maxHeap.poll()
            i += 2
        }
    }
}

class Solution {
    func wiggleSort(_ nums: inout [Int]) {
        var sorted = nums.sorted(by: >)
        var idx = 0

        var i = 1
        while i < nums.count {
            nums[i] = sorted[idx]
            idx += 1
            i += 2
        }
        i = 0
        while i < nums.count {
            nums[i] = sorted[idx]
            idx += 1
            i += 2
        }
    }
}

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

2. Sorting

Intuition

After sorting the array, we can create the wiggle pattern by swapping adjacent pairs starting from index 1. When we swap elements at positions 1 and 2, then 3 and 4, and so on, we create local peaks at odd indices. This works because after sorting, swapping pushes the slightly larger element to the odd index position.

Algorithm

Sort the array in ascending order.
Iterate through the array starting at index 1, incrementing by 2 each time.
At each step, swap the current element with the next element.
After processing all pairs, the array satisfies the wiggle sort property.

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

        nums.sort()
        for i in range(1, len(nums) - 1, 2):
            nums[i], nums[i + 1] = nums[i + 1], nums[i]

public class Solution {
    public void wiggleSort(int[] nums) {
        Arrays.sort(nums);
        for (int i = 1; i < nums.length - 1; i += 2) {
            int temp = nums[i];
            nums[i] = nums[i + 1];
            nums[i + 1] = temp;
        }
    }
}

class Solution {
    /**
     * @param {number[]} nums
     * @return {void} Do not return anything, modify nums in-place instead.
     */
    wiggleSort(nums) {
        nums.sort((a, b) => a - b);
        for (let i = 1; i < nums.length - 1; i += 2) {
            [nums[i], nums[i + 1]] = [nums[i + 1], nums[i]];
        }
    }
}

public class Solution {
    public void WiggleSort(int[] nums) {
        Array.Sort(nums);
        for (int i = 1; i < nums.Length - 1; i += 2) {
            int temp = nums[i];
            nums[i] = nums[i + 1];
            nums[i + 1] = temp;
        }
    }
}

class Solution {
    fun wiggleSort(nums: IntArray) {
        nums.sort()
        var i = 1
        while (i < nums.size - 1) {
            val temp = nums[i]
            nums[i] = nums[i + 1]
            nums[i + 1] = temp
            i += 2
        }
    }
}

class Solution {
    func wiggleSort(_ nums: inout [Int]) {
        nums.sort()
        var i = 1
        while i < nums.count - 1 {
            nums.swapAt(i, i + 1)
            i += 2
        }
    }
}

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(1)$ or $O(n)$ depending on the sorting algorithm.

3. Greedy - I

Intuition

We can achieve wiggle sort in a single pass by observing the required relationship at each index. At odd indices, the element should be greater than or equal to its predecessor. At even indices, the element should be less than or equal to its predecessor. If these conditions are violated, we simply swap with the previous element to fix the relationship locally without affecting previously processed elements.

Algorithm

Iterate through the array starting from index 1.
For odd indices: if the current element is less than the previous element, swap them.
For even indices: if the current element is greater than the previous element, swap them.
Return the modified array which now satisfies the wiggle property.

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 == 1 and nums[i] < nums[i - 1]) or
                (i % 2 == 0 and nums[i] > nums[i - 1])
            ):
                nums[i], nums[i - 1] = nums[i - 1], nums[i]

class Solution {
    /**
     * @param {number[]} nums
     * @return {void} Do not return anything, modify nums in-place instead.
     */
    wiggleSort(nums) {
        for (let i = 1; i < nums.length; i++) {
            if (
                (i % 2 == 1 && nums[i] < nums[i - 1]) ||
                (i % 2 == 0 && nums[i] > nums[i - 1])
            ) {
                [nums[i], nums[i - 1]] = [nums[i - 1], nums[i]];
            }
        }
    }
}

Time & Space Complexity

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

4. Greedy - II

Intuition

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.

Algorithm

Iterate through the array starting from index 1.
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]).
If the XOR of these two values is true (they differ), swap the current element with the previous one.
The array is wiggle sorted after one complete pass.

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 {
    /**
     * @param {number[]} nums
     * @return {void} Do not return anything, modify nums in-place instead.
     */
    wiggleSort(nums) {
        for (var i = 1; i < nums.length; i++) {
            if (i % 2 ^ (nums[i] > nums[i - 1])) {
                [nums[i], nums[i - 1]] = [nums[i - 1], nums[i]];
            }
        }
    }
}

func wiggleSort(nums []int) {
    for i := 1; i < len(nums); i++ {
        cmp := 0
        if nums[i] > nums[i-1] {
            cmp = 1
        }
        if (i%2)^cmp != 0 {
            nums[i], nums[i-1] = nums[i-1], nums[i]
        }
    }
}

class Solution {
    fun wiggleSort(nums: IntArray) {
        for (i in 1 until nums.size) {
            val cmp = if (nums[i] > nums[i - 1]) 1 else 0
            if ((i % 2) xor cmp != 0) {
                val temp = nums[i]
                nums[i] = nums[i - 1]
                nums[i - 1] = temp
            }
        }
    }
}

class Solution {
    func wiggleSort(_ nums: inout [Int]) {
        for i in 1..<nums.count {
            let cmp = nums[i] > nums[i - 1] ? 1 : 0
            if (i % 2) ^ cmp != 0 {
                nums.swapAt(i, i - 1)
            }
        }
    }
}

Time & Space Complexity

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

Common Pitfalls

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.

# This problem (Wiggle Sort): allows equality
# nums[i] <= nums[i+1] for odd i
# nums[i] >= nums[i+1] for even i

# Wiggle Sort II: requires strict inequality
# nums[i] < nums[i+1] for odd i (different problem!)

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.

# Wrong: comparing with next element and swapping forward
if i % 2 == 1 and nums[i] < nums[i + 1]:
    nums[i], nums[i + 1] = nums[i + 1], nums[i]

# Correct: comparing with previous element
if i % 2 == 1 and nums[i] < nums[i - 1]:
    nums[i], nums[i - 1] = nums[i - 1], nums[i]

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].

# Wrong: causes index error at nums[-1]
for i in range(len(nums)):
    if nums[i] > nums[i - 1]:  # i=0 gives nums[-1]

# Correct: start from index 1
for i in range(1, len(nums)):
    if nums[i] > nums[i - 1]: