LeetCode 324 - Wiggle Sort II

The problem asks us to rearrange an array so that it follows a strict alternating pattern: - nums[0] < nums[1] - nums[1] nums[2] - nums[2] < nums[3] - and so on. This pattern is called a wiggle sequence because the values repeatedly go up and down.

leetcodemediumarraydivide-and-conquergreedysortingquickselect

LeetCode Problem 324

Difficulty: 🟡 Medium
Topics: Array, Divide and Conquer, Greedy, Sorting, Quickselect

Solution

Problem Understanding

The problem asks us to rearrange an array so that it follows a strict alternating pattern:

  • nums[0] < nums[1]
  • nums[1] > nums[2]
  • nums[2] < nums[3]
  • and so on.

This pattern is called a wiggle sequence because the values repeatedly go up and down.

The input is an integer array nums, and we must modify it in-place. The problem guarantees that at least one valid arrangement always exists.

A key detail is that the inequalities are strict. Equal adjacent values are not allowed in positions where either < or > is required. This makes duplicates particularly important to handle carefully.

The constraints allow arrays up to 5 * 10^4 elements, which means an O(n^2) solution would likely time out. We need something close to linear or O(n log n).

The follow-up asks for an O(n) time solution with O(1) extra space. This strongly hints at using:

  • Quickselect to find the median in linear time
  • Careful in-place partitioning
  • A special indexing trick to place large and small values correctly

Several edge cases can cause bugs in naive implementations:

  • Arrays with many duplicate values, such as [1,1,1,2,2,2]
  • Arrays where the median appears many times
  • Very small arrays
  • Already wiggle-sorted arrays
  • Arrays where direct adjacent swapping fails to maintain strict inequalities

The guarantee that a valid answer always exists simplifies the problem slightly because we never need to detect impossible cases.

Approaches

Brute Force Approach

A straightforward solution is:

  1. Sort the array.
  2. Split it into two halves.
  3. Interleave the smaller half and larger half.

For example:

  • Sorted: [1,1,1,4,5,6]
  • Smaller half: [1,1,1]
  • Larger half: [4,5,6]

Then place values alternately:

  • even indices get smaller values
  • odd indices get larger values

To avoid duplicates ending up adjacent, we fill from the end of each half instead of from the beginning.

This works because:

  • Odd positions must contain relatively larger values
  • Even positions must contain relatively smaller values
  • Reversing both halves spreads duplicates apart

This approach is correct and much easier to implement, but sorting costs O(n log n) time and usually requires extra space if we build a temporary array.

Optimal Approach

The optimal solution achieves:

  • O(n) average time
  • O(1) extra space

The key insight is that the final wiggle pattern is fundamentally determined by the median.

If we know the median:

  • Values larger than the median should go into odd positions
  • Values smaller than the median should go into even positions
  • Values equal to the median fill the remaining spots

This resembles the Dutch National Flag partitioning problem.

However, directly partitioning the array is not enough because the physical indices do not align with the wiggle requirements. We therefore use a virtual indexing trick.

The virtual index mapping:

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

reorders traversal so that:

  • odd positions are filled first
  • even positions are filled afterward

This guarantees that larger elements naturally land in wiggle peak positions.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n log n) O(n) Sort and interleave two halves
Optimal O(n) average O(1) Quickselect + three-way partition + virtual indexing

Algorithm Walkthrough

Optimal Algorithm

  1. Find the median of the array using Quickselect.

The median acts as the dividing line between small and large values. Elements greater than the median should occupy odd indices, while smaller elements should occupy even indices. 2. Define a virtual index mapping.

Instead of accessing index i directly, we use:

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

This mapping visits indices in the order:

1, 3, 5, 0, 2, 4

for even-length arrays.

This ordering ensures that larger elements are placed into odd indices first. 3. Perform a three-way partition around the median.

We maintain three regions:

  • Left region contains values greater than the median
  • Middle region contains values equal to the median
  • Right region contains values smaller than the median

This is identical in spirit to the Dutch National Flag algorithm. 4. Use three pointers:

  • left tracks where the next large value should go
  • i scans the array
  • right tracks where the next small value should go
  1. While scanning:

  • If the current value is greater than the median:

  • swap it into the left region

  • move both left and i

  • If the current value is smaller than the median:

  • swap it into the right region

  • move right

  • do not advance i yet because the swapped-in value still needs processing

  • If the current value equals the median:

  • simply advance i

  1. Because all accesses use virtual indices, large values automatically move into odd positions and small values move into even positions.

Why it works

The wiggle condition requires peaks at odd indices and valleys at even indices.

The virtual indexing scheme guarantees that odd indices are processed first. During partitioning:

  • values larger than the median move toward the front of virtual order
  • values smaller than the median move toward the back

As a result:

  • odd positions receive large values
  • even positions receive small values

Values equal to the median safely occupy remaining positions without violating the wiggle structure.

The strict inequalities hold because all larger values are separated from smaller values by construction.

Python Solution

from typing import List
import random

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

        n = len(nums)

        def kth_smallest(k: int) -> int:
            left, right = 0, n - 1

            while True:
                pivot_index = random.randint(left, right)
                pivot = nums[pivot_index]

                # Three-way partition
                nums[pivot_index], nums[right] = nums[right], nums[pivot_index]

                store_index = left

                for i in range(left, right):
                    if nums[i] < pivot:
                        nums[store_index], nums[i] = nums[i], nums[store_index]
                        store_index += 1

                nums[store_index], nums[right] = nums[right], nums[store_index]

                if store_index == k:
                    return nums[store_index]
                elif store_index < k:
                    left = store_index + 1
                else:
                    right = store_index - 1

        median = kth_smallest(n // 2)

        def virtual_index(i: int) -> int:
            return (1 + 2 * i) % (n | 1)

        left = 0
        i = 0
        right = n - 1

        while i <= right:
            mapped_i = virtual_index(i)

            if nums[mapped_i] > median:
                mapped_left = virtual_index(left)

                nums[mapped_left], nums[mapped_i] = (
                    nums[mapped_i],
                    nums[mapped_left],
                )

                left += 1
                i += 1

            elif nums[mapped_i] < median:
                mapped_right = virtual_index(right)

                nums[mapped_right], nums[mapped_i] = (
                    nums[mapped_i],
                    nums[mapped_right],
                )

                right -= 1

            else:
                i += 1

The implementation begins by finding the median using Quickselect. Instead of fully sorting the array, Quickselect repeatedly partitions the array until the median position is identified.

After finding the median, the solution defines the virtual indexing function. This mapping is the core trick of the problem because it transforms a standard three-way partition into a wiggle-aware rearrangement.

The algorithm then performs Dutch National Flag partitioning:

  • values greater than the median move left
  • values smaller than the median move right
  • median values remain in the middle

The important detail is that all reads and writes use virtual indices instead of physical indices. This guarantees the final wiggle order.

The solution modifies the array in-place and uses only constant extra memory.

Go Solution

package main

import (
	"math/rand"
)

func wiggleSort(nums []int) {
	n := len(nums)

	kthSmallest := func(k int) int {
		left, right := 0, n-1

		for {
			pivotIndex := left + rand.Intn(right-left+1)
			pivot := nums[pivotIndex]

			nums[pivotIndex], nums[right] = nums[right], nums[pivotIndex]

			storeIndex := left

			for i := left; i < right; i++ {
				if nums[i] < pivot {
					nums[storeIndex], nums[i] = nums[i], nums[storeIndex]
					storeIndex++
				}
			}

			nums[storeIndex], nums[right] = nums[right], nums[storeIndex]

			if storeIndex == k {
				return nums[storeIndex]
			} else if storeIndex < k {
				left = storeIndex + 1
			} else {
				right = storeIndex - 1
			}
		}
	}

	median := kthSmallest(n / 2)

	virtualIndex := func(i int) int {
		return (1 + 2*i) % (n | 1)
	}

	left, i, right := 0, 0, n-1

	for i <= right {
		mappedI := virtualIndex(i)

		if nums[mappedI] > median {
			mappedLeft := virtualIndex(left)

			nums[mappedLeft], nums[mappedI] =
				nums[mappedI], nums[mappedLeft]

			left++
			i++

		} else if nums[mappedI] < median {
			mappedRight := virtualIndex(right)

			nums[mappedRight], nums[mappedI] =
				nums[mappedI], nums[mappedRight]

			right--

		} else {
			i++
		}
	}
}

The Go implementation closely mirrors the Python solution. Go slices are mutable references, so modifications happen in-place automatically.

One small implementation detail is random pivot generation. Go uses rand.Intn() to choose a pivot index during Quickselect.

The virtual indexing logic and three-way partitioning remain identical to the Python version.

Worked Examples

Example 1

Input:

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

Step 1: Find Median

Sorted order:

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

Median:

4

Step 2: Virtual Index Order

For n = 6:

virtual indices:
1, 3, 5, 0, 2, 4

Step 3: Partition Around Median

Iteration Current Value Action Array State
Start - Initial [1,5,1,1,6,4]
1 5 > 4 Move left [1,5,1,1,6,4]
2 1 < 4 Move right [1,5,1,4,6,1]
3 4 = 4 Keep middle [1,5,1,4,6,1]
4 6 > 4 Move left [1,5,1,6,4,1]

Final valid arrangement:

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

Check:

1 < 5 > 1 < 6 > 1 < 4

Valid.

Example 2

Input:

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

Step 1: Find Median

Sorted:

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

Median:

2

Step 2: Partition

Iteration Current Value Action Array State
Start - Initial [1,3,2,2,3,1]
1 3 > 2 Move left [1,3,2,2,3,1]
2 2 = 2 Keep middle [1,3,2,2,3,1]
3 2 = 2 Keep middle [1,3,2,2,3,1]
4 3 > 2 Move left [2,3,1,3,1,2]

Final arrangement:

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

Check:

2 < 3 > 1 < 3 > 1 < 2

Valid.

Complexity Analysis

Measure Complexity Explanation
Time O(n) average Quickselect and partitioning are both linear on average
Space O(1) Rearrangement happens entirely in-place

The dominant operations are:

  • Quickselect median finding
  • Three-way partitioning

Both process the array linearly. Quickselect has worst-case O(n^2) complexity, but randomized pivot selection gives expected linear performance.

The algorithm uses only a few pointers and temporary variables, so extra memory usage remains constant.

Test Cases

from typing import List

def is_wiggle(nums: List[int]) -> bool:
    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

# Example 1
nums = [1, 5, 1, 1, 6, 4]
Solution().wiggleSort(nums)
assert is_wiggle(nums)  # standard example

# Example 2
nums = [1, 3, 2, 2, 3, 1]
Solution().wiggleSort(nums)
assert is_wiggle(nums)  # duplicates around median

# Small array
nums = [1, 2]
Solution().wiggleSort(nums)
assert is_wiggle(nums)  # minimum nontrivial case

# Many duplicates
nums = [4, 5, 5, 6]
Solution().wiggleSort(nums)
assert is_wiggle(nums)  # repeated values

# Odd length
nums = [1, 1, 2, 2, 3]
Solution().wiggleSort(nums)
assert is_wiggle(nums)  # odd-sized input

# Already wiggle sorted
nums = [1, 3, 2, 4, 3, 5]
Solution().wiggleSort(nums)
assert is_wiggle(nums)  # should remain valid

# Large repeated median
nums = [1, 2, 2, 2, 3, 3]
Solution().wiggleSort(nums)
assert is_wiggle(nums)  # many median duplicates

# Descending order
nums = [6, 5, 4, 3, 2, 1]
Solution().wiggleSort(nums)
assert is_wiggle(nums)  # reverse-sorted input

Test Summary

Test Why
[1,5,1,1,6,4] Standard example
[1,3,2,2,3,1] Duplicate-heavy case
[1,2] Smallest meaningful input
[4,5,5,6] Adjacent duplicates
[1,1,2,2,3] Odd-length array
[1,3,2,4,3,5] Already wiggle-sorted
[1,2,2,2,3,3] Median appears multiple times
[6,5,4,3,2,1] Reverse-sorted input

Edge Cases

Arrays With Many Duplicate Values

Inputs like [1,1,1,2,2,2] are difficult because equal elements can easily end up adjacent, violating strict inequalities.

A naive adjacent-swap solution often fails here. The virtual indexing strategy avoids this by separating equal median values across the array while forcing larger values into odd positions.

Arrays Where the Median Appears Frequently

Cases such as [1,2,2,2,3,3] are particularly tricky because the median dominates the array.

The three-way partition correctly groups:

  • larger values
  • median values
  • smaller values

without disturbing the wiggle structure. Median values naturally fill leftover slots safely.

Very Small Arrays

Small arrays such as [1,2] or [2,1] can expose indexing bugs or off-by-one errors.

The implementation handles these naturally because:

  • Quickselect still works correctly
  • Virtual indexing remains valid
  • The partition loop terminates immediately when appropriate

Reverse-Sorted Arrays

Arrays in descending order may look far from a wiggle arrangement.

However, because the algorithm depends only on relative comparison with the median, the initial order does not matter. The partitioning process completely reorganizes the array into the required alternating structure.