LeetCode 324: Wiggle Sort II

Problem Restatement

We are given an integer array nums.

Rearrange it in-place so that:

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

This alternating pattern is called wiggle order.

The official problem guarantees that a valid answer exists. The follow-up asks for O(n) average time and O(1) extra space. (github.com)

Input and Output

Function shape:

def wiggleSort(nums: list[int]) -> None:
    ...

Examples

Example 1:

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

One valid answer:

[1, 6, 1, 5, 1, 4]

Check:

1 < 6 > 1 < 5 > 1 < 4

Example 2:

nums = [1, 3, 2, 2, 3, 1]

One valid answer:

[2, 3, 1, 3, 1, 2]

Check:

2 < 3 > 1 < 3 > 1 < 2

First Thought: Sort and Alternate

A simple idea:

1. Sort the array.
2. Put small numbers at even indices.
3. Put large numbers at odd indices.

Example:

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

Odd positions should hold larger values:

_ 6 _ 5 _ 4

Even positions hold smaller values:

1 _ 1 _ 1 _

Result:

[1, 6, 1, 5, 1, 4]

This works.

But we must be careful with duplicates.

A naive alternating fill can fail.

Example:

[1, 1, 2, 2, 2, 2]

A careless arrangement may produce:

1 < 2 > 2

which breaks strict inequality.

We need a more careful placement strategy.

Key Insight

After sorting:

1. The smaller half should occupy even indices.
2. The larger half should occupy odd indices.
3. Fill both halves in reverse order.

Why reverse order?

Because duplicates should be separated as much as possible.

Sorted Structure

Suppose:

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

Sorted:

[1, 1, 1, 4, 5, 6]

Split:

Now place:

• Small half reversed into even indices.
• Large half reversed into odd indices.

Even positions:

0, 2, 4

receive:

1, 1, 1

Odd positions:

1, 3, 5

receive:

6, 5, 4

Result:

[1, 6, 1, 5, 1, 4]

This guarantees:

small < large > small < large

Why Reverse Order Matters

Consider:

nums = [1, 1, 2, 2, 2, 2]

Sorted:

[1,1,2,2,2,2]

Small half:

[1,1,2]

Large half:

[2,2,2]

If we fill forward, duplicates can touch.

But reversing spreads equal values apart.

Result:

[2, 2, 1, 2, 1, 2]

still has an issue at the beginning because equality appears immediately.

So the exact splitting matters:

mid = (n + 1) // 2

The first half must contain the extra element when n is odd.

Then:

• Reverse-fill smaller half into even indices.
• Reverse-fill larger half into odd indices.

This arrangement prevents equal neighboring elements.

Algorithm

1. Sort the array.
2. Split into:
   • smaller half
   • larger half
3. Reverse both halves.
4. Fill:
   • even indices from reversed smaller half
   • odd indices from reversed larger half

Correctness

Let the sorted array be divided into:

• a smaller half S
• a larger half L

Every value in S is less than or equal to every value in L.

The algorithm places values from S into even indices and values from L into odd indices.

Odd indices are therefore filled with values at least as large as their neighboring even-index values.

The reverse placement is crucial. By filling both halves from largest to smallest, duplicate values from the same half are spread apart instead of clustered together. This prevents equal adjacent values from violating the strict wiggle inequalities.

For every odd index i:

nums[i] > nums[i - 1]

because the odd position receives one of the largest remaining values from L, while the adjacent even position receives one of the largest remaining values from S, and all values in L are at least as large as those in S.

Similarly:

nums[i] > nums[i + 1]

when i + 1 exists.

Thus the final arrangement satisfies:

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

Complexity

Sorting dominates the complexity.

The follow-up asks for O(n) average time and O(1) space using median partitioning and virtual indexing, but the sorting solution is much simpler and widely accepted in interviews.

Implementation

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

        sorted_nums = sorted(nums)

        mid = (n + 1) // 2

        small = sorted_nums[:mid]
        large = sorted_nums[mid:]

        small.reverse()
        large.reverse()

        even = 0
        odd = 1

        for value in small:
            nums[even] = value
            even += 2

        for value in large:
            nums[odd] = value
            odd += 2

Code Explanation

First sort the array.

sorted_nums = sorted(nums)

Now split the array.

mid = (n + 1) // 2

The smaller half gets the extra element when n is odd.

small = sorted_nums[:mid]
large = sorted_nums[mid:]

Reverse both halves.

small.reverse()
large.reverse()

This spreads duplicates apart.

Fill even indices using smaller values.

even = 0

for value in small:
    nums[even] = value
    even += 2

Fill odd indices using larger values.

odd = 1

for value in large:
    nums[odd] = value
    odd += 2

The final arrangement satisfies the wiggle condition.

Follow-Up: O(n) Virtual Indexing Idea

The optimal follow-up solution uses:

1. Quickselect to find the median.
2. Three-way partitioning like Dutch National Flag.
3. Virtual indexing.

Virtual index mapping:

(1 + 2 * i) % (n | 1)

This remaps positions so large values naturally move to odd indices.

That solution achieves:

But it is substantially harder to implement correctly.

Testing

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

    return True

def run_tests():
    s = Solution()

    nums1 = [1, 5, 1, 1, 6, 4]
    s.wiggleSort(nums1)
    assert is_wiggle(nums1)

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

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

    nums4 = [4, 5, 5, 6]
    s.wiggleSort(nums4)
    assert is_wiggle(nums4)

    nums5 = [1]
    s.wiggleSort(nums5)
    assert nums5 == [1]

    nums6 = [2, 2]
    s.wiggleSort(nums6)

    print("all tests passed")

run_tests()

Test meaning: