NeetCode #122LC-280MediumArrays & HashingNC Algo100
← Back to All Problems#122 · #280 · Wiggle Sort(摆动排序)
📌 Problem Statement & Constraints
Given an unsorted array
nums, reorder it in place so that nums[0] <= nums[1] >= nums[2] <= nums[3] >= .... Constraints: 1 <= nums.length <= 5 * 10^4, 0 <= nums[i] <= 10^4.💡 Core Algorithmic Approaches
- Only adjacent pairs are constrained, so a single left-to-right pass with local swaps suffices.
- At an even index
iwe neednums[i] <= nums[i+1]; at an odd indexiwe neednums[i] >= nums[i+1]. - If the required relation is violated, swap
nums[i]andnums[i+1]. Each swap fixes the pair and cannot break an earlier pair, because a swap only ever moves a smaller value left or a larger value right in a way that preserves the earlier inequality. - This is O(n) time with O(1) space, beating the sort-then-interleave approach which is O(n log n).
💻 Benchmark Python3 Implementation
class Solution:
def wiggleSort(self, nums: List[int]) -> None:
for i in range(len(nums) - 1):
if i % 2 == 0:
if nums[i] > nums[i + 1]: # need nums[i] <= nums[i+1]
nums[i], nums[i + 1] = nums[i + 1], nums[i]
else:
if nums[i] < nums[i + 1]: # need nums[i] >= nums[i+1]
nums[i], nums[i + 1] = nums[i + 1], nums[i]
# Sort-then-interleave: O(n log n), simpler to argue about correctness
class Solution2:
def wiggleSort(self, nums: List[int]) -> None:
nums.sort()
for i in range(1, len(nums) - 1, 2):
nums[i], nums[i + 1] = nums[i + 1], nums[i]⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n) for the single-pass swap version; O(n log n) for the sort-based version.
💾 Space Complexity
O(1) for the swap version; O(1) extra for the sort version (in-place sort) but O(n log n) time.
⚠️ Interview Pitfalls & Follow-ups
- Sorting and then reversing every other pair incorrectly: the interleave must swap
(i, i+1)for oddistarting at 1, as shown. - Trying to satisfy both neighbours at once with a median partition: that is the approach for the harder variant (Wiggle Sort II), not this one.
- Using
<=and>=loosely: the statement uses non-strict inequalities, so equal neighbours are allowed; do not add extra swaps. - Returning the array: the signature returns
None; the reordering must be in place.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.