Wiggle Sort
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 ≤ 10⁵
- −10⁹ ≤ nums[i] ≤ 10⁹
Example
nums = [3, 5, 2, 1, 6, 4][3, 5, 1, 6, 2, 4]Starting from index 1 (odd), nums[1] = 5 is greater than nums[0] = 3 and nums[2] = 1. At index 2 (even), nums[2] = 1 is less than nums[1] = 5 and nums[3] = 6. The algorithm iterates through the array, and at each index, it enforces the wiggle property by swapping elements if the condition is violated. For example, at index 1 (odd), since nums[1] < nums[0], they are swapped to maintain nums[1] >= nums[0]. This local correction ensures the global wiggle pattern emerges by the end of the single pass.
Approach
Straightforward Solution
A naive approach might sort the array and then rearrange elements by interleaving smaller and larger halves, which requires O(n log n) time and extra space, violating the in-place constraint.
Core Observation
The wiggle property requires alternating inequalities between adjacent elements, which can be enforced locally by comparing pairs of elements at each step. This local enforcement guarantees the global pattern without sorting or complex rearrangements.
Path to Optimal
PreviewThe key insight is that the wiggle property can be maintained by a single pass through the array, swapping adjacent elements whenever the local wiggle condition is violated…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewIterate through the array starting from index 1. For odd indices, ensure nums[i] >= nums[i-1]; if not, swap them…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n)
The algorithm makes a single pass through the array, performing at most one swap per element, resulting in linear time complexity.
Space
O(1)
All operations are done in-place with only a few variables for iteration and swapping, requiring constant auxiliary space.
Pattern Spotlight
Greedy Algorithms (Local Correction)
Enforce the global alternating inequality pattern by locally correcting pairs in a single pass, swapping only when the immediate wiggle condition is violated, which guarantees the entire array satisfies the wiggle property efficiently.
Solution
| 1 | class Solution: |
| 2 | def wiggleSort(self, nums: list[int]) -> None: |
| 3 | for i in range(1, len(nums)): |
| 4 | if i % 2 == 1: |
| 5 | if nums[i] < nums[i - 1]: |
| 6 | nums[i], nums[i - 1] = nums[i - 1], nums[i] |
| 7 | else: |
| 8 | if nums[i] > nums[i - 1]: |
| 9 | nums[i], nums[i - 1] = nums[i - 1], nums[i] |
Step-by-Step Solution
Iterate Through Array to Enforce Wiggle Property at Odd Indices
| 3 | for i in range(1, len(nums)): |
| 4 | if i % 2 == 1: |
| 5 | if nums[i] < nums[i - 1]: |
| 6 | nums[i], nums[i - 1] = nums[i - 1], nums[i] |
Objective
To ensure that elements at odd indices are greater than or equal to their immediate predecessors by swapping when necessary.
Key Insight
At odd indices, the wiggle property requires nums[i] >= nums[i-1]. If this is violated, swapping the two elements locally restores the correct order. This local fix is sufficient because it only affects the current pair and preserves the wiggle property established in previous steps.
Interview Quick-Check
Core Logic
For odd indices, check if nums[i] < nums[i-1]; if so, swap to enforce nums[i] >= nums[i-1], maintaining the wiggle pattern.
State & Boundaries
Start iteration from index 1 to compare each element with its predecessor.
Common Pitfalls & Bugs
Failing to swap when the condition is violated at odd indices leads to incorrect wiggle ordering.
Enforce Wiggle Property at Even Indices by Local Swapping
To ensure that elements at even indices are less than or equal to their immediate predecessors by swapping when necessary.
1 more step with full analysis available on Pro.
Line Analysis
This solution has 4 Critical lines interviewers watch for.
if nums[i] < nums[i - 1]:For odd indices, check if the current element is less than the previous element.
If nums[i] < nums[i-1] at an odd index, the wiggle property nums[i] >= nums[i-1] is violated and must be corrected.
nums[i], nums[i - 1] = nums[i - 1], nums[i]Swap elements at indices i and i-1 to restore the wiggle property at odd indices.
Swapping locally corrects the order, ensuring nums[i] >= nums[i-1] without affecting the rest of the array, enabling a single-pass solution.
if nums[i] > nums[i - 1]:For even indices, check if the current element is greater than the previous element.
If nums[i] > nums[i-1] at an even index, the wiggle property nums[i] <= nums[i-1] is violated and must be corrected.
Full line-by-line criticality + rationale for all 7 lines available on Pro.
Test Your Understanding
Why does enforcing the wiggle condition locally at each index guarantee the entire array satisfies the wiggle property?
See the answer with Pro.
Related Problems
Greedy pattern
Don't just read it. Drill it.
Reconstruct Wiggle Sort from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Wiggle Sort drill