LeetCode 280: Wiggle Sort

Problem Restatement

We are given an unsorted integer array nums.

We need to reorder it in-place so that it follows this pattern:

nums[0] <= nums[1] >= nums[2] <= nums[3] >= nums[4] ...

So the values should alternate between low and high.

The problem asks us to modify nums directly and return nothing. The input is guaranteed to have at least one valid answer.

Input and Output

Function shape:

class Solution:
    def wiggleSort(self, nums: list[int]) -> None:
        ...

Examples

For:

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

One valid output is:

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

Check the pattern:

3 <= 5
5 >= 1
1 <= 6
6 >= 2
2 <= 4

Another valid output could also be accepted. The problem only requires the array to satisfy the wiggle pattern.

For:

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

The array already satisfies:

6 <= 6 >= 5 <= 6 >= 3 <= 8

So it may remain unchanged.

First Thought: Sort First

A simple idea is to sort the array first.

For example:

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

After sorting:

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

Then we can swap each adjacent pair starting from index 1:

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

This satisfies:

1 <= 3 >= 2 <= 5 >= 4 <= 6

Code:

class Solution:
    def wiggleSort(self, nums: list[int]) -> None:
        nums.sort()

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

This works, but sorting costs O(n log n).

The follow-up asks whether we can solve it in O(n) time.

Key Insight

We only need each neighboring pair to satisfy the local rule.

For index i, compare nums[i] with nums[i - 1].

If i is odd, then nums[i] should be greater than or equal to nums[i - 1].

nums[i - 1] <= nums[i]

If i is even, then nums[i] should be less than or equal to nums[i - 1].

nums[i - 1] >= nums[i]

Whenever this local rule is violated, we swap the two adjacent elements.

That single swap fixes the relationship at position i - 1 and i.

Algorithm

Scan from left to right, starting at index 1.

For each index i:

If i is odd, we need:

nums[i] >= nums[i - 1]

If this is false, swap them.

If i is even, we need:

nums[i] <= nums[i - 1]

If this is false, swap them.

After the scan finishes, the whole array satisfies the wiggle condition.

Correctness

We prove that after processing index i, the prefix nums[0:i+1] satisfies the required wiggle pattern.

For i = 1, the algorithm checks whether nums[0] <= nums[1]. If the condition fails, it swaps the two values, so the condition becomes true.

Now assume the prefix ending at i - 1 already satisfies the pattern.

When processing index i, the algorithm only checks the relationship between nums[i - 1] and nums[i].

If i is odd, it ensures:

nums[i - 1] <= nums[i]

If i is even, it ensures:

nums[i - 1] >= nums[i]

If no swap is needed, the prefix remains valid.

If a swap is needed, the new value placed at i - 1 still preserves the previous relationship with nums[i - 2].

For an odd i, the violation means nums[i] < nums[i - 1]. Swapping places the smaller value at even index i - 1, which can only help the previous <= valley relation.

For an even i, the violation means nums[i] > nums[i - 1]. Swapping places the larger value at odd index i - 1, which can only help the previous >= peak relation.

So the previous prefix remains valid, and the new adjacent pair becomes valid.

By induction, after the last index is processed, the entire array satisfies the wiggle pattern.

Complexity

Implementation

class Solution:
    def wiggleSort(self, nums: list[int]) -> None:
        for i in range(1, len(nums)):
            should_be_peak = i % 2 == 1

            if should_be_peak and nums[i] < nums[i - 1]:
                nums[i], nums[i - 1] = nums[i - 1], nums[i]

            if not should_be_peak and nums[i] > nums[i - 1]:
                nums[i], nums[i - 1] = nums[i - 1], nums[i]

Code Explanation

We start from index 1 because every rule compares the current element with the previous one:

for i in range(1, len(nums)):

Odd indices should be peaks:

should_be_peak = i % 2 == 1

If i is odd but nums[i] is smaller than the previous value, the peak rule is violated:

if should_be_peak and nums[i] < nums[i - 1]:
    nums[i], nums[i - 1] = nums[i - 1], nums[i]

If i is even but nums[i] is larger than the previous value, the valley rule is violated:

if not should_be_peak and nums[i] > nums[i - 1]:
    nums[i], nums[i - 1] = nums[i - 1], nums[i]

The function returns nothing because the array is modified in-place.

Testing

def is_wiggle(nums):
    for i in range(len(nums) - 1):
        if i % 2 == 0:
            if nums[i] > nums[i + 1]:
                return False
        else:
            if nums[i] < nums[i + 1]:
                return False

    return True

def test_wiggle_sort():
    s = Solution()

    nums = [3, 5, 2, 1, 6, 4]
    s.wiggleSort(nums)
    assert is_wiggle(nums)

    nums = [6, 6, 5, 6, 3, 8]
    s.wiggleSort(nums)
    assert is_wiggle(nums)

    nums = [1]
    s.wiggleSort(nums)
    assert is_wiggle(nums)

    nums = [2, 1]
    s.wiggleSort(nums)
    assert is_wiggle(nums)

    nums = [1, 1, 1, 1]
    s.wiggleSort(nums)
    assert is_wiggle(nums)

    print("all tests passed")

test_wiggle_sort()

Test meaning: