Wiggle Sort II
Problem
Given an integer array nums, reorder it in-place such that nums[0] <= nums[1] >= nums[2] <= nums[3] >= nums[4] <= ...
- 1 ≤ nums.length ≤ 5 * 10⁴
- 0 ≤ nums[i] ≤ 5000
Example
nums = [1, 5, 1, 1, 6, 4][1, 6, 1, 5, 1, 4]The algorithm first sorts the array to get [1,1,1,4,5,6]. It then splits the sorted array into two halves: small = [1,1,1] and large = [4,5,6]. By placing the largest elements from small and large alternately starting from the end, it produces a wiggle pattern: indices 0,2,4 get values from small in descending order, and indices 1,3,5 get values from large in descending order. This ensures nums[0] <= nums[1] >= nums[2] <= nums[3] >= nums[4] <= nums[5].
Approach
Straightforward Solution
A brute-force approach would attempt to reorder elements by swapping adjacent pairs repeatedly until the wiggle condition is met, which can be inefficient and complex to implement correctly.
Core Observation
The wiggle property requires alternating elements to be less than or equal to and greater than or equal to their neighbors. Sorting the array reveals the relative order of elements, enabling a controlled interleaving of smaller and larger halves to satisfy the wiggle condition.
Path to Optimal
PreviewSorting the array provides a clear ordering. Splitting into two halves and then placing elements from the smaller half at even indices and from the larger half at odd indices, both in descending order, guarantees the wiggle property…
Full step-by-step walkthrough on Pro →
Optimal Approach
Sort the array, split it into two halves (small and large), then fill the original array by placing elements from the end of small at even indices and from the end of large at odd indices. This interleaving ensures the wiggle pattern is maintained throughout the array.
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n log n)
Sorting the array dominates the runtime with O(n log n). The subsequent interleaving is a single pass O(n) operation.
Space
O(n)
Auxiliary space is used to store the sorted copy and the two halves. The in-place rearrangement modifies the original array but requires O(n) extra space for the sorted arrays.
Pattern Spotlight
Sorting with Controlled Interleaving
Sorting reveals the global order, and by splitting and interleaving halves in reverse order, the wiggle property is guaranteed without complex swaps or multiple passes.
Solution
| 1 | class Solution: |
| 2 | def wiggleSort(self, nums: list[int]) -> None: |
| 3 | sorted_nums = sorted(nums) |
| 4 | mid = (len(nums) + 1) // 2 |
| 5 | |
| 6 | small = sorted_nums[:mid] |
| 7 | large = sorted_nums[mid:] |
| 8 | |
| 9 | small_i = len(small) - 1 |
| 10 | large_i = len(large) - 1 |
| 11 | |
| 12 | for i in range(len(nums)): |
| 13 | if i % 2 == 0: |
| 14 | nums[i] = small[small_i] |
| 15 | small_i -= 1 |
| 16 | else: |
| 17 | nums[i] = large[large_i] |
| 18 | large_i -= 1 |
Step-by-Step Solution
Sort and Partition the Array into Small and Large Halves
| 3 | sorted_nums = sorted(nums) |
| 4 | mid = (len(nums) + 1) // 2 |
| 6 | small = sorted_nums[:mid] |
| 7 | large = sorted_nums[mid:] |
Objective
To create two sorted subarrays representing the smaller and larger halves of the original array.
Key Insight
Sorting the array reveals the global order of elements. Splitting it at the midpoint ensures the smaller half contains elements that are less than or equal to those in the larger half. This partitioning is essential to interleave elements to satisfy the wiggle property.
Interview Quick-Check
Core Logic
Sorting and splitting the array into two halves allows controlled interleaving of smaller and larger elements to enforce the wiggle pattern.
Common Pitfalls & Bugs
Incorrectly calculating the midpoint or splitting the array can break the wiggle property, especially for arrays with odd length.
Interleave Elements from Small and Large Halves in Reverse Order
To fill the original array by placing elements from the small half at even indices and from the large half at odd indices, both starting from their ends.
1 more step with full analysis available on Pro.
Line Analysis
This solution has 3 Critical lines interviewers watch for.
sorted_nums = sorted(nums)Create a sorted copy of the input array.
Sorting reveals the global order of elements, which is essential for partitioning and controlled interleaving to achieve the wiggle pattern.
nums[i] = small[small_i]Assign the current even index with the element from the smaller half at small_i.
Placing the largest remaining element from the smaller half at even indices ensures nums[even] <= nums[odd] in the final array.
nums[i] = large[large_i]Assign the current odd index with the element from the larger half at large_i.
Placing the largest remaining element from the larger half at odd indices ensures nums[odd] >= nums[even] in the final array.
Full line-by-line criticality + rationale for all 13 lines available on Pro.
Test Your Understanding
Why does placing elements from the smaller half at even indices and from the larger half at odd indices, both in descending order, guarantee the wiggle property?
See the answer with Pro.
Related Problems
Sorting pattern
Don't just read it. Drill it.
Reconstruct Wiggle Sort II from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Wiggle Sort II drill