⚡Flashcard Drill➔
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

  1. Only adjacent pairs are constrained, so a single left-to-right pass with local swaps suffices.
  2. At an even index i we need nums[i] <= nums[i+1]; at an odd index i we need nums[i] >= nums[i+1].
  3. If the required relation is violated, swap nums[i] and nums[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.
  4. 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 odd i starting 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.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems