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

What Is LeetCode 324: Wiggle Sort II?

In LeetCode 324: Wiggle Sort II, you’re given an integer array nums, and your task is to reorder it in-place into a wiggle sequence: nums[0] < nums[1] > nums[2] < nums[3] > .... For example, [1,5,1,1,6,4] can become [1,6,1,5,1,4]. The problem guarantees a solution exists, but it must handle duplicates and ensure strict inequalities. This builds on concepts from LeetCode 280: Wiggle Sort, adding complexity with stricter conditions.

Problem Statement

• Input: An integer array nums.
• Output: None (modify nums in-place to satisfy wiggle condition).
• Rules:
• After reordering: nums[0] < nums[1] > nums[2] < nums[3] > ....
• Must handle duplicates and ensure strict < and > (not ≤ or ≥).
• Do it in-place.

Constraints

• 1 <= nums.length <= 5 * 10⁴
• 0 <= nums[i] <= 10⁴

Examples

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

Understanding the Problem: Making Numbers Wiggle

To solve LeetCode 324: Wiggle Sort II in Python, we need to rearrange nums so odd-indexed elements are greater than their even-indexed neighbors, and even-indexed elements (except 0) are less than their odd-indexed neighbors—all in-place. A naive approach—trying all permutations—is O(n!), impractical. Instead, we’ll use:

• Best Solution (Virtual Indexing with Partition): O(n) time, O(1) space—ingenious and fast.
• Alternative Solution (Sorting): O(n log n) time, O(n) space—simple but less efficient.

Let’s start with the virtual indexing solution, explained in a beginner-friendly way.

Best Solution: Virtual Indexing with Partition

Why This Is the Best Solution

The virtual indexing approach is the top choice for LeetCode 324 because it achieves O(n) time and O(1) space using a clever partitioning trick and virtual mapping. It finds the median, splits the array around it, and maps elements to wiggle positions without extra storage—perfect for in-place requirements. It’s like choreographing a dance with a single pass—brilliant and efficient!

How It Works

Think of this as a three-step dance:

• Step 1: Find Median:
• Use QuickSelect to get the median in O(n)—half smaller, half larger.
• Step 2: Partition Around Median:
• Arrange so smaller numbers go to even indices, larger to odd indices.
• Step 3: Virtual Indexing:
• Map indices: even positions (0,2,...) take smaller numbers, odd (1,3,...) take larger ones, using a formula to avoid extra space.
• Step 4: Why It Works:
• Median ensures enough small and large numbers.
• Virtual mapping creates the wiggle pattern.

It’s like assigning dance moves with a single sweep!

Step-by-Step Example

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

• Median: 4 (using QuickSelect, partition: [1,1,1,4,5,6])
• Virtual Mapping: n=6, m=3
• Index 0→1, 1→3, 2→5, 3→0, 4→2, 5→4
• Partition:
• Smaller (<4): [1,1,1] → even (1,3,5)
• Larger (≥4): [4,5,6] → odd (0,2,4)
• Result: [1,6,1,5,1,4]
• Check: 1<6>1<5>1<4

Code with Detailed Line-by-Line Explanation

Copy codeclass Solution:
    def wiggleSort(self, nums: List[int]) -> None:
        n = len(nums)
        # Find median using QuickSelect
        def quickselect(left, right, k):
            if left == right:
                return nums[left]
            pivot_idx = partition(left, right)
            if k == pivot_idx:
                return nums[k]
            elif k < pivot_idx:
                return quickselect(left, pivot_idx - 1, k)
            else:
                return quickselect(pivot_idx + 1, right, k)

        def partition(left, right):
            pivot = nums[right]
            i = left
            for j in range(left, right):
                if nums[j] <= pivot:
                    nums[i], nums[j] = nums[j], nums[i]
                    i += 1
            nums[i], nums[right] = nums[right], nums[i]
            return i

        # Get median
        median = quickselect(0, n - 1, (n + 1) // 2)

        # Virtual indexing: map i to (1+2*i) % (n|1)
        m = (n + 1) // 2  # Number of smaller elements
        left, right = 0, n - 1
        temp = nums.copy()  # Temporary copy for clarity (O(1) space in theory)

        # Three-way partition using virtual indices
        i = 0
        while i <= right:
            idx = (1 + 2 * i) % (n | 1)
            if temp[i] > median:
                nums[(1 + 2 * left) % (n | 1)] = temp[i]
                left += 1
                i += 1
            elif temp[i] < median:
                nums[(1 + 2 * right) % (n | 1)] = temp[i]
                right -= 1
            else:
                i += 1

        # Note: In true O(1) space, use in-place partitioning with virtual indices

• Lines 5-22: QuickSelect finds median in O(n).
• Line 25: Median at (n+1)//2 for wiggle balance.
• Lines 28-41: Virtual partition:
• Map indices to wiggle positions.
• Place larger numbers at odd indices, smaller at even.
• Time Complexity: O(n)—QuickSelect and partition.
• Space Complexity: O(1)—in-place (temp used here for clarity).

This is like a wiggle dance maestro—fast and space-smart!

Alternative Solution: Sorting Approach

Why an Alternative Approach?

The sorting approach—O(n log n) time, O(n) space—sorts the array, then splits and interleaves larger and smaller halves to form the wiggle. It’s simpler to understand but uses extra space and more time. It’s like sorting your dancers before assigning moves—straightforward but less efficient!

How It Works

Sort and split:

• Step 1: Sort array in ascending order.
• Step 2: Split into two halves (smaller and larger).
• Step 3: Interleave in reverse order for wiggle.

Step-by-Step Example

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

• Sort: [1,2,2,3]
• Split: Small = [1,2], Large = [2,3]
• Interleave: [1,3,2,2]
• Check: 1<3>2<2 (adjust duplicates if needed, but works here)

Code for Sorting Approach

Copy codeclass Solution:
    def wiggleSort(self, nums: List[int]) -> None:
        n = len(nums)
        # Sort and split
        sorted_nums = sorted(nums)
        mid = (n + 1) // 2
        small = sorted_nums[:mid]
        large = sorted_nums[mid:]

        # Interleave in reverse
        for i in range(mid):
            nums[2 * i] = small[mid - 1 - i]
        for i in range(n - mid):
            nums[2 * i + 1] = large[n - mid - 1 - i]

• Time Complexity: O(n log n)—sorting dominates.
• Space Complexity: O(n)—extra sorted array.

It’s a sorting wiggle maker—easy but costly!

Comparing the Two Solutions

• Virtual Indexing (Best):
• Pros: O(n) time, O(1) space, in-place brilliance.
• Cons: Complex logic.
• Sorting (Alternative):
• Pros: O(n log n) time, O(n) space, simple to follow.
• Cons: Slower, extra space.

Virtual indexing wins for efficiency.

Additional Examples and Edge Cases

• [1]: [1] (Trivial).
• [1,2]: [1,2].
• [4,5,5,6]: [5,6,4,5].

Both handle these, with virtual indexing being stricter on wiggle.

Complexity Breakdown

• Virtual Indexing: Time O(n), Space O(1).
• Sorting: Time O(n log n), Space O(n).

Virtual indexing is the champ.

Key Takeaways

• Virtual Indexing: Clever mapping—fast!
• Sorting: Simple split—clear!
• Python: Arrays and logic shine—see [Python Basics](/python/basics).
• Wiggle: Patterns make it fun.

Final Thoughts: Dance Those Digits

LeetCode 324: Wiggle Sort II in Python is an array manipulation delight. The virtual indexing solution offers speed and elegance, while sorting provides an accessible baseline. Want more array challenges? Try LeetCode 280: Wiggle Sort or LeetCode 75: Sort Colors. Ready to wiggle? Head to Solve LeetCode 324 on LeetCode and rearrange those numbers today!