Introduction
LeetCode 280: Wiggle Sort is a neat greedy and array manipulation problem. You're given an unsorted array, and your task is to rearrange it such that it follows the wiggle property:
nums[0] ≤ nums[1] ≥ nums[2] ≤ nums[3] ≥ nums[4] ...
The challenge is to do this in-place with O(n) time complexity.
Problem Statement
Rearrange an unsorted array nums into wiggle order, where the numbers alternate between less-than and greater-than relationships.
There is no need to return a new array. Modify the input list in-place.
Example
python
Input: nums = [3, 5, 2, 1, 6, 4]
Output: [3, 5, 1, 6, 2, 4]
Explanation: Follows pattern nums[0] ≤ nums[1] ≥ nums[2] ≤ nums[3] ...
Note: Multiple correct answers are possible as long as the wiggle property is preserved.
✅ Step-by-Step Solution
🧠 Key Insight
We don’t need full sorting! We can solve it using a greedy one-pass swap:
- Iterate over the array
- At each index
i:
- If
i is even: ensure nums[i] ≤ nums[i+1]
- If
i is odd: ensure nums[i] ≥ nums[i+1]
- If not, swap the two elements
This maintains the wiggle pattern locally, and that's all we need!
✅ Python Code
python
class Solution:
def wiggleSort(self, nums: list[int]) -> None:
for i in range(len(nums) - 1):
if (i % 2 == 0 and nums[i] > nums[i + 1]) or \
(i % 2 == 1 and nums[i] < nums[i + 1]):
nums[i], nums[i + 1] = nums[i + 1], nums[i]
This modifies the list in-place. No extra space is used.
🧪 Dry Run Example
Input: [3, 5, 2, 1, 6, 4]
- i=0 (even): 3 ≤ 5 → ✅
- i=1 (odd): 5 ≥ 2 → ✅
- i=2 (even): 2 ≤ 1 → ❌ → swap →
[3, 5, 1, 2, 6, 4]
- i=3 (odd): 2 ≥ 6 → ❌ → swap →
[3, 5, 1, 6, 2, 4]
- i=4 (even): 2 ≤ 4 → ✅
Final: [3, 5, 1, 6, 2, 4] ✅
⏱️ Time and Space Complexity
MetricValueTime ComplexityO(n)Space ComplexityO(1)In-Place✅ Yes
🔍 Edge Cases
- Empty array → do nothing
- Single element → already satisfies wiggle
- Already wiggle-sorted array → no swaps needed
✅ Conclusion
LeetCode 280: Wiggle Sort is a beautiful example of solving a pattern-based array problem without sorting, using greedy logic and local decisions. It’s a frequent interview favorite due to:
- Efficiency (O(n) time)
- Simplicity (1-pass)
- Real-world implications (UI layout, alternating bar heights, etc.)