Problem Description
Given an integer array nums, reorder it such that nums[0] <= nums[1] >= nums[2] <= nums[3] ... . It is guaranteed that the input always has a valid answer.
Key Insights
- The alternating "wiggle" requirement can be satisfied by ensuring two conditions:
- For every odd index i, nums[i] should be greater than or equal to nums[i-1].
- For every even index i (where i > 0), nums[i] should be less than or equal to nums[i-1].
- A single pass through the array can ensure these conditions by swapping adjacent elements when the condition is violated.
- This greedy approach works because the local adjustments guarantee the overall wiggle pattern without needing to sort the entire array.
Space and Time Complexity
Time Complexity: O(n) — Only one pass through the array is needed. Space Complexity: O(1) — The modifications are done in-place without extra data structures.
Solution
We can achieve a wiggle sort in one pass by iterating through the array and, at each index i (starting from 1), checking if the pair (nums[i-1], nums[i]) satisfies the wiggle condition. If i is odd, nums[i] should be at least nums[i-1]; if not, we swap them. Conversely, if i is even and nums[i] is greater than nums[i-1], then we swap them. These local swaps adjust the order incrementally while ensuring that the overall wiggle pattern is maintained. This greedy approach works because only two adjacent numbers are involved in any violation and fixing them locally does not disturb the rest of the order.