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 = [1,5,1,1,6,4] Output: [1,6,1,5,1,4] Explanation: [1,4,1,5,1,6] is also accepted.
Example 2:
Input: nums = [1,3,2,2,3,1] Output: [2,3,1,3,1,2]
Constraints:
1 <= nums.length <= 5 * 1040 <= nums[i] <= 5000nums.O(n) time and/or in-place with O(1) extra space?The goal of Wiggle Sort II is to reorder the array so that nums[0] < nums[1] > nums[2] < nums[3].... A common starting point is a sorting-based approach, where the array is sorted and then elements are interleaved from the two halves to enforce the alternating pattern. While simple to implement, this method requires extra space and runs in O(n log n) time.
A more optimal idea uses Quickselect to find the median in O(n) average time. Once the median is known, a three-way partition (Dutch National Flag technique) can be applied to separate elements less than, equal to, and greater than the median. To maintain the wiggle property, elements are placed using a virtual indexing trick that maps indices to positions ensuring larger numbers occupy odd indices and smaller numbers occupy even indices.
This strategy achieves O(n) average time with O(1) extra space and is the approach typically expected in advanced interview settings.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sorting and Interleaving | O(n log n) | O(n) |
| Quickselect + Three-Way Partition | O(n) average | O(1) |
NeetCode
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Wiggle Sort II is considered a classic medium-to-hard interview problem that tests array manipulation, partitioning, and selection algorithms. Variants of this question have appeared in interviews at large tech companies.
The median helps split the array into elements greater than, equal to, and less than a central value. By distributing these groups strategically, we can enforce the alternating less-than and greater-than pattern required for wiggle order.
The optimal approach uses Quickselect to find the median and then performs a three-way partition around it. A virtual indexing trick ensures that larger numbers go to odd indices and smaller numbers to even indices, maintaining the wiggle property. This method runs in O(n) average time with constant extra space.
The problem mainly relies on array manipulation techniques rather than specialized data structures. Concepts like Quickselect, three-way partitioning, and index remapping are more important than additional data structures.