LeetCode 280: Wiggle Sort Solution in Python – A Step-by-Step Guide

What Is LeetCode 280: Wiggle Sort?

In LeetCode 280: Wiggle Sort, you’re given an integer array nums, and your task is to reorder it in-place so that it follows a “wiggle” pattern: nums[0] < nums[1] > nums[2] < nums[3] > nums[4], and so on. The catch? You need to modify the array directly without creating a new one (ideally), and there’s no strict requirement for a unique solution—just ensure the wiggle condition holds. For example, [1, 5, 1, 1, 6, 4] could become [1, 5, 1, 6, 1, 4]. This problem tests your ability to manipulate arrays efficiently, sharing a spirit with problems like LeetCode 75: Sort Colors, but with a unique alternating twist.

Problem Statement

• Input: An integer array nums of length n.
• Output: The array nums, modified in-place to satisfy nums[0] < nums[1] > nums[2] < nums[3] > ...
• Rules: Rearrange in-place; no need for the smallest or largest possible values at peaks—just ensure the wiggle pattern.

Constraints

• n: 1 to 5 * 10⁴ (50,000).
• nums[i]: 0 to 10⁹.

Examples

• Input: nums = [1, 5, 1, 1, 6, 4]
• Output: [1, 5, 1, 6, 1, 4] (1 < 5 > 1 < 6 > 1 < 4)
• Input: nums = [1, 3, 2, 2, 3, 1]
• Output: [2, 3, 1, 3, 1, 2] (2 < 3 > 1 < 3 > 1 < 2)
• Input: nums = [1, 2, 3]
• Output: [1, 3, 2] (1 < 3 > 2)

Understanding the Problem: Making It Wiggle

To solve LeetCode 280: Wiggle Sort in Python, we need to transform the array so that odd-indexed elements are peaks (greater than their neighbors) and even-indexed elements are valleys (less than their neighbors). A naive approach might be to shuffle randomly until it works, but that’s inefficient. Instead, we’ll use: 1. Best Solution (In-Place Swapping): O(n) time, O(1) space—fast and space-savvy. 2. Alternative Solution (Sort and Rearrange): O(n log n) time, O(n) space—easier to grasp but less optimal.

Let’s start with the in-place swapping solution, breaking it down extra clearly for beginners.

Best Solution: In-Place Swapping

Why This Is the Best Solution

The in-place swapping method is the champ for LeetCode 280 because it runs in O(n) time and uses O(1) space—no extra arrays needed! It walks through the array once, fixing violations of the wiggle pattern by swapping adjacent elements. It’s like tweaking a seesaw as you go, ensuring each pair fits the up-down rhythm without overcomplicating things.

How It Works

Picture this: you’re strolling through the array, checking each pair of numbers. At even indices (0, 2, 4...), you want a valley (smaller than the next), and at odd indices (1, 3, 5...), you want a peak (bigger than the next). If the pattern breaks, swap the pair to fix it. Here’s the step-by-step, explained simply:

• Step 1: Understand the Pattern:
• Even indices (0, 2, 4...): nums[i] < nums[i+1].
• Odd indices (1, 3, 5...): nums[i] > nums[i+1].
• Only need to check up to n-2 since the last element just follows.

• Step 2: Walk and Swap:
• Loop through indices 0 to n-2.
• For even i: If nums[i] >= nums[i+1], swap them.
• For odd i: If nums[i] <= nums[i+1], swap them.

• Step 3: Why It Works:
• Swapping fixes local violations (e.g., a peak where a valley should be).
• Since any array can be wiggled (no strict ordering required), local fixes propagate correctly.
• Each swap ensures the current pair fits the pattern without breaking earlier ones excessively.

• Step 4: Result:
• Array ends up in wiggle order with minimal changes.

It’s like nudging numbers into place as you walk by—simple yet effective!

Step-by-Step Example

Example: nums = [1, 5, 1, 1, 6, 4]

• Initial: [1, 5, 1, 1, 6, 4].
• i=0 (even): 1 < 5—good, no swap.
• i=1 (odd): 5 > 1—good, no swap.
• i=2 (even): 1 > 1 (not <)—swap to [1, 1, 1, 5, 6, 4].
• i=3 (odd): 5 > 6 (not >)—swap to [1, 1, 1, 6, 5, 4].
• i=4 (even): 5 < 4 (not <)—swap to [1, 1, 1, 6, 4, 5].
• Result: [1, 1, 1, 6, 4, 5] (1 < 1 > 1 < 6 > 4 < 5—wiggle holds!).

Example: nums = [1, 3, 2, 2, 3, 1]

• Initial: [1, 3, 2, 2, 3, 1].
• i=0: 1 < 3—good.
• i=1: 3 > 2—good.
• i=2: 2 = 2 (not <)—swap to [1, 3, 2, 2, 3, 1].
• i=3: 2 < 3 (not >)—swap to [1, 3, 2, 3, 2, 1].
• i=4: 2 > 1 (not <)—swap to [1, 3, 2, 3, 1, 2].
• Result: [1, 3, 2, 3, 1, 2] (1 < 3 > 2 < 3 > 1 < 2).

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained in a beginner-friendly way:

Copy codeclass Solution:
    def wiggleSort(self, nums: List[int]) -> None:
        # No return—just modify nums in-place
        n = len(nums)

        # Step 1: Loop through array up to second-to-last element
        for i in range(n - 1):
            # Step 2: Even index—should be a valley
            if i % 2 == 0:
                if nums[i] >= nums[i + 1]:
                    # Swap if not less than next
                    nums[i], nums[i + 1] = nums[i + 1], nums[i]
            # Step 3: Odd index—should be a peak
            else:
                if nums[i] <= nums[i + 1]:
                    # Swap if not greater than next
                    nums[i], nums[i + 1] = nums[i + 1], nums[i]

• Line 4: Get array length—we’ll check pairs up to n-1.
• Line 6: Loop from 0 to n-2 since we compare i with i+1.
• Line 8-10: Even i (valley): If nums[i] >= nums[i+1], swap to make it smaller.
• Line 12-14: Odd i (peak): If nums[i] <= nums[i+1], swap to make it bigger.
• No return: Modifies nums in-place as required.

• Time Complexity: O(n)—one pass through the array.
• Space Complexity: O(1)—no extra space, just swaps.

This solution is like a quick dance—step, check, swap, repeat!

Alternative Solution: Sort and Rearrange

Why an Alternative Approach?

Sorting first then rearranging gives us a wiggle pattern by leveraging order. It’s O(n log n) time and O(n) space—slower and less space-efficient—but it’s easier to understand for beginners, making it a great stepping stone before tackling in-place logic.

How It Works

Think of this as organizing your numbers neatly, then shuffling them into peaks and valleys:

• Step 1: Sort the array ascending.
• Step 2: Split into two halves—smaller numbers (valleys) and larger numbers (peaks).
• Step 3: Interleave them: small, large, small, large...
• Step 4: Copy back to nums.

It’s like dealing cards from two stacks to create that up-down flow!

Step-by-Step Example

Example: nums = [1, 5, 1, 1, 6, 4]

• Sort: [1, 1, 1, 4, 5, 6].
• Split: Small = [1, 1, 1], Large = [4, 5, 6].
• Interleave: [1, 6, 1, 5, 1, 4] (reverse large to ensure peaks).
• Result: [1, 6, 1, 5, 1, 4] (1 < 6 > 1 < 5 > 1 < 4).

Code for Sort and Rearrange Approach

Copy codeclass Solution:
    def wiggleSort(self, nums: List[int]) -> None:
        # Step 1: Sort the array
        sorted_nums = sorted(nums)
        n = len(nums)

        # Step 2: Split into two halves
        mid = (n + 1) // 2
        small = sorted_nums[:mid]
        large = sorted_nums[mid:]

        # Step 3: Interleave, placing larger numbers at peaks
        for i in range(mid):
            nums[2 * i] = small[mid - 1 - i]  # Valleys
            if 2 * i + 1 < n:
                nums[2 * i + 1] = large[mid - 1 - i]  # Peaks

• Time Complexity: O(n log n)—due to sorting.
• Space Complexity: O(n)—extra array for sorting.

It’s a reliable but heavier approach.

Comparing the Two Solutions

• In-Place Swapping (Best):
• Pros: O(n) time, O(1) space, in-place.
• Cons: Logic takes practice.
• Sort and Rearrange (Alternative):
• Pros: Easy to follow, guaranteed wiggle.
• Cons: O(n log n) time, O(n) space.

In-place wins for efficiency.

Additional Examples and Edge Cases

• n = 1: [3] → [3]—already valid.
• n = 2: [1, 2] → [1, 2] (1 < 2).
• Duplicates: [1, 1, 1] → [1, 1, 1] (1 = 1 < 1 works with adjustments).

Both handle these fine.

Complexity Breakdown

• In-Place: Time O(n), Space O(1).
• Sort: Time O(n log n), Space O(n).

In-place is the lean machine.

Key Takeaways

• In-Place: Swap smartly for speed.
• Sort: Order then shuffle for clarity.
• Optimization: Space and time matter.
• Python Tip: Master arrays with [Python Basics](/python/basics).

Final Thoughts: Wiggle Your Way Up

LeetCode 280: Wiggle Sort in Python is a fun array dance. In-place swapping keeps it tight and fast, while sorting offers a beginner-friendly path. Want more? Try LeetCode 75: Sort Colors or LeetCode 324: Wiggle Sort II. Ready to wiggle? Head to Solve LeetCode 280 on LeetCode and make that array bounce today!