Rearrange nums such that nums[0] < nums[1] > nums[2] < nums[3] ... (wiggle order).

Examples

Example:

Input: nums = [1,5,1,1,6,4]
Output: [1,6,1,5,1,4]
Explanation: 1 < 6 > 1 < 5 > 1 < 4

Constraints

  • 1 <= nums.length <= 5 * 10^4
  • 0 <= nums[i] <= 5000

Thinking Process

  • nth_element finds the median in average O(n) time
  • 3-way partition handles duplicates correctly
  • Virtual indexing avoids overwriting placements by distributing indices across the array cyclically
Array + hash map 2 7 11 map hash map for O(1) lookups

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Prefix sum O(n) O(n) Range queries, subarray sum
Sort + scan (this problem) O(n log n) O(1) Intervals, meeting rooms
Kadane’s algorithm O(n) O(1) Maximum subarray
Hash map counting O(n) O(n) Frequency, two-sum variants

Solution

Time Complexity: O(n) average (due to nth_element)
Space Complexity: O(1) extra

Steps:

  • Find the median in-place using nth_element (average O(n))
  • Use a 3-way partition (Dutch National Flag) around the median
  • Apply a virtual index mapping vi(i) = (1 + 2*i) % (n | 1) so that larger numbers go to odd indices and smaller ones to even indices, achieving wiggle order
class Solution:
    def wiggleSort(self, nums):
        n = len(nums)

        nums.sort()
        midIt = n // 2
        median = nums[midIt]

        def vi(i):
            return (1 + 2 * i) % (n | 1)

        left = 0
        right = n - 1
        i = 0

        while i <= right:
            if nums[vi(i)] > median:
                nums[vi(left)], nums[vi(i)] = nums[vi(i)], nums[vi(left)]
                left += 1
                i += 1
            elif nums[vi(i)] < median:
                nums[vi(i)], nums[vi(right)] = nums[vi(right)], nums[vi(i)]
                right -= 1
            else:
                i += 1

Solution Explanation

Approach: Sort + scan (this problem)

Key idea: nth_element finds the median in average O(n) time

How the code works:

  • nth_element finds the median in average O(n) time
  • 3-way partition handles duplicates correctly
  • Virtual indexing avoids overwriting placements by distributing indices across the array cyclically

    Why Virtual Indexing Works

  • The mapping vi(i) = (1 + 2*i) % (n | 1) interleaves indices so that large elements are placed at positions 1, 3, 5, … and small elements at 0, 2, 4, …
  • Partitioning by median ensures elements greater than median occupy odd positions, and elements less than median occupy even positions, satisfying wiggle constraints.

Edge Cases

  • All elements equal → already wiggle (no swaps needed)
  • Many duplicates → 3-way partition around median is essential
  • Small arrays (n <= 2) → already satisfy or trivially adjustable
  • [280. Wiggle Sort] — simpler version without strict inequality
  • [75. Sort Colors] — Dutch National Flag
  • [215. Kth Largest Element in an Array] — nth_element

Common Mistakes

  • Skipping edge cases (empty input, single element, boundaries).
  • Off-by-one errors in loops and index ranges.
  • Forgetting to handle the case when no valid answer exists.

Key Takeaways

  • nth_element finds the median in average O(n) time
  • 3-way partition handles duplicates correctly
  • Virtual indexing avoids overwriting placements by distributing indices across the array cyclically

References

Template Reference