280. Wiggle Sort - Solution & Explanation

Q: Is Wiggle Sort easy or hard?

Wiggle Sort is considered a medium-level problem. The brute-force idea using sorting is straightforward, but recognizing that the wiggle condition can be enforced with a single greedy pass requires stronger problem-solving insight.

Q: Wiggle Sort Python/Java solution

In Python or Java, implement a single loop from index 1 to n-1 and compare each element with its predecessor. Depending on whether the index is odd or even, swap the pair when the inequality condition is violated. The logic is identical across languages and runs in O(n) time.

Q: How to solve Wiggle Sort in O(n)?

Traverse the array from index 1 to n-1. For each index i, check the wiggle condition: if i is odd and nums[i] nums[i-1], swap them. Each swap fixes the local ordering without breaking previous pairs, so the entire array becomes wiggle-sorted in one pass.

The problem

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⁴
0 <= nums[i] <= 10⁴
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?

Approach overview

Problem Overview: You are given an integer array and must reorder it in-place so that it follows a wiggle pattern: nums[0] <= nums[1] >= nums[2] <= nums[3] .... Any valid arrangement that satisfies the alternating relationship is acceptable.

Approach 1: Sort and Swap Adjacent Pairs (O(n log n) time, O(1) space)

The most direct solution starts by sorting the array. After sorting, iterate through the array starting from index 1 and swap every pair (i, i+1). Because the array is sorted, swapping adjacent elements creates the alternating high-low pattern required for wiggle order. This approach relies on sorting to guarantee that each local pair satisfies the condition after swapping. It’s easy to implement and works reliably, though the O(n log n) sorting step makes it slower than necessary.

Approach 2: One-Pass Greedy Swap (O(n) time, O(1) space)

A more efficient method scans the array once and fixes violations locally. For each index i, check whether the wiggle condition is satisfied. If i is odd, ensure nums[i] >= nums[i-1]. If i is even, ensure nums[i] <= nums[i-1]. When the condition fails, swap the two elements. This works because fixing the local pair does not break the previously established pattern. The technique is a classic greedy strategy: enforce the constraint immediately while iterating through the array. Since each element is visited once and swaps are constant-time, the total complexity is O(n) with O(1) extra space.

Approach 3: Sort + Interleaving Variant (O(n log n) time, O(n) space)

Another interpretation splits the sorted array into two halves and interleaves smaller and larger elements. This guarantees the alternating inequality pattern by placing relatively larger values at odd indices and smaller ones at even indices. The idea appears in variations of wiggle problems where stricter ordering is required. For this specific problem it is usually unnecessary, but it helps illustrate how ordering constraints can be enforced structurally after sorting.

Recommended for interviews: The one-pass greedy approach is the expected solution. Interviewers want to see that you recognize the wiggle constraint can be enforced locally while iterating. Starting with the sorting approach shows clear reasoning, but the O(n) greedy pass demonstrates stronger algorithmic insight and better performance.

Solution

Python

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]

Java

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

    private void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}

C++

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

func wiggleSort(nums []int) {
	for i := 1; i < len(nums); 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]
		}
	}
}

Try this approach in the editor

Complexity analysis

Approach	Time	Space	When to Use
Sort and Swap Adjacent Pairs	O(n log n)	O(1)	Simple implementation when optimal performance is not required
One-Pass Greedy Swap	O(n)	O(1)	Best general solution; expected in coding interviews
Sort + Interleaving	O(n log n)	O(n)	Useful when building wiggle ordering explicitly from sorted halves

Frequently asked questions

Is Wiggle Sort easy or hard?

Wiggle Sort is considered a medium-level problem. The brute-force idea using sorting is straightforward, but recognizing that the wiggle condition can be enforced with a single greedy pass requires stronger problem-solving insight.

Wiggle Sort Python/Java solution

In Python or Java, implement a single loop from index 1 to n-1 and compare each element with its predecessor. Depending on whether the index is odd or even, swap the pair when the inequality condition is violated. The logic is identical across languages and runs in O(n) time.

How to solve Wiggle Sort in O(n)?

Traverse the array from index 1 to n-1. For each index i, check the wiggle condition: if i is odd and nums[i] < nums[i-1], swap them; if i is even and nums[i] > nums[i-1], swap them. Each swap fixes the local ordering without breaking previous pairs, so the entire array becomes wiggle-sorted in one pass.

What is the best approach for Wiggle Sort?

The best approach is a one-pass greedy traversal. Iterate through the array and enforce the wiggle rule at each index: odd indices should be greater than or equal to the previous element, and even indices should be less than or equal to the previous element. Swap adjacent elements whenever the rule is violated. This runs in O(n) time with O(1) extra space.

Is Wiggle Sort asked at Google/Amazon/Meta?

Wiggle-style array rearrangement problems appear in interviews at companies like Google, Amazon, and Meta. They test understanding of greedy strategies, in-place array manipulation, and reasoning about local constraints that maintain global ordering patterns.

What data structure is used in Wiggle Sort?

The problem primarily uses arrays with in-place element swaps. The optimal solution relies on a greedy traversal rather than additional data structures, which keeps the space complexity at O(1). Sorting-based solutions may use the language’s built-in sorting implementation.

What is the time complexity of Wiggle Sort?

Two common solutions exist. Sorting the array and then swapping adjacent elements takes O(n log n) time due to the sort step. The optimal greedy solution scans the array once and performs constant-time swaps, resulting in O(n) time and O(1) space.

Wiggle Sort solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Wiggle Sort solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Related problems