Problem Description

You are given an integer array nums. Your task is to reorder the array elements in-place so that they follow a "wiggle" pattern where:

• The element at even index is smaller than the element at the next odd index
• The element at odd index is greater than the element at the next even index

In other words, the pattern should be: nums[0] < nums[1] > nums[2] < nums[3] > nums[4] < nums[5]...

The problem guarantees that the input array will always have a valid answer, meaning it's always possible to arrange the elements to satisfy this wiggle pattern.

The solution approach sorts the array first, then strategically places elements from two different portions of the sorted array. It uses two pointers: one starting from the middle of the sorted array moving backward (for even indices), and another starting from the end of the sorted array moving backward (for odd indices). This ensures that smaller elements from the first half are placed at even positions, and larger elements from the second half are placed at odd positions, creating the required wiggle pattern.

For example, if the sorted array is [1, 2, 3, 4, 5, 6], the algorithm would place elements like:

• Even indices (0, 2, 4): get elements from position (n-1)/2 backward: 3, 2, 1
• Odd indices (1, 3, 5): get elements from position n-1 backward: 6, 5, 4
• Result: [3, 6, 2, 5, 1, 4] which satisfies 3 < 6 > 2 < 5 > 1 < 4

Intuition

To create a wiggle pattern where elements alternate between being smaller and larger than their neighbors, we need to carefully think about how to distribute the values in the array.

The key insight is that if we sort the array first, we can divide it into two halves: smaller elements and larger elements. To avoid having equal adjacent elements (which would violate the strict inequality requirement), we need to interleave these two halves in a specific way.

Why does simply alternating between small and large halves work? Consider a sorted array like [1, 2, 3, 4, 5, 6]. If we naively take elements from the beginning of each half ([1, 2, 3] and [4, 5, 6]) and alternate them, we might get [1, 4, 2, 5, 3, 6]. This works, but there's a subtle issue: if we have duplicate values around the middle (like [1, 2, 3, 3, 4, 5]), placing elements from the start of each half could put equal values next to each other.

The clever trick is to take elements from the end of each half, moving backward. By taking from the middle position (n-1)/2 backward for even indices and from the last position n-1 backward for odd indices, we maximize the "distance" between selected values. This ensures that:

• Elements at even positions come from the smaller half (but starting from its largest values)
• Elements at odd positions come from the larger half (starting from its largest values)
• Adjacent elements are as far apart as possible in the sorted order, minimizing the chance of placing equal values next to each other

This backward traversal strategy guarantees that we create valid "peaks" and "valleys" in the wiggle pattern, with each peak being strictly greater than its neighboring valleys, and each valley being strictly less than its neighboring peaks.

Solution Approach

The implementation follows a three-step process:

Step 1: Sort the array

arr = sorted(nums)

We create a sorted copy of the input array. This allows us to identify which elements should go into the "smaller" half and which into the "larger" half.

Step 2: Initialize two pointers

i, j = (n - 1) >> 1, n - 1

• Pointer i starts at the middle index (n-1) >> 1 (equivalent to (n-1) // 2). This pointer will traverse the first half of the sorted array backward.
• Pointer j starts at the last index n - 1. This pointer will traverse the second half of the sorted array backward.

Step 3: Place elements alternately

for k in range(n):
    if k % 2 == 0:
        nums[k] = arr[i]
        i -= 1
    else:
        nums[k] = arr[j]
        j -= 1

We iterate through each position in the original array:

• For even indices (k % 2 == 0): Place elements from the first half by using pointer i, then decrement i
• For odd indices: Place elements from the second half by using pointer j, then decrement j

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

1. After sorting: arr = [1, 1, 1, 4, 5, 6]
2. Initialize: i = 2 (pointing to arr[2] = 1), j = 5 (pointing to arr[5] = 6)
3. Fill positions:
   • k=0 (even): nums[0] = arr[2] = 1, i becomes 1
   • k=1 (odd): nums[1] = arr[5] = 6, j becomes 4
   • k=2 (even): nums[2] = arr[1] = 1, i becomes 0
   • k=3 (odd): nums[3] = arr[4] = 5, j becomes 3
   • k=4 (even): nums[4] = arr[0] = 1, i becomes -1
   • k=5 (odd): nums[5] = arr[3] = 4, j becomes 2
4. Result: nums = [1, 6, 1, 5, 1, 4] which satisfies 1 < 6 > 1 < 5 > 1 < 4

The time complexity is O(n log n) due to sorting, and the space complexity is O(n) for storing the sorted array.

Example Walkthrough

Let's walk through a small example with nums = [3, 5, 2, 1, 6, 4] to illustrate the solution approach.

Step 1: Sort the array First, we create a sorted copy:

arr = [1, 2, 3, 4, 5, 6]

Step 2: Initialize two pointers

n = 6
i = (6-1) >> 1 = 2  (points to arr[2] = 3)
j = 6-1 = 5         (points to arr[5] = 6)

Step 3: Place elements alternately Now we fill each position in the original array:

Final result: nums = [3, 6, 2, 5, 1, 4]

Verification of wiggle pattern:

• nums[0] < nums[1]: 3 < 6 ✓
• nums[1] > nums[2]: 6 > 2 ✓
• nums[2] < nums[3]: 2 < 5 ✓
• nums[3] > nums[4]: 5 > 1 ✓
• nums[4] < nums[5]: 1 < 4 ✓

The key insight here is that by taking elements from the end of each half moving backward, we ensure maximum separation between adjacent elements. The smaller half contributes {3, 2, 1} to even positions, while the larger half contributes {6, 5, 4} to odd positions, creating the required alternating pattern of peaks and valleys.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n log n)

The dominant operation in this algorithm is the sorting step arr = sorted(nums), which takes O(n log n) time where n is the length of the input array. After sorting, the algorithm performs a single pass through the array to rearrange elements, which takes O(n) time. Therefore, the overall time complexity is O(n log n) + O(n) = O(n log n).

Space Complexity: O(n)

The algorithm creates a sorted copy of the input array arr = sorted(nums), which requires O(n) additional space to store all n elements. The remaining variables (i, j, k, n) use only O(1) constant space. Therefore, the total space complexity is O(n).

Common Pitfalls

Pitfall: Failing to Handle Duplicate Elements Correctly

The most critical pitfall in this problem occurs when the array contains many duplicate elements, especially when duplicates appear around the median value. Simply placing elements from the sorted array's two halves might create adjacent equal elements, violating the strict inequality requirement of the wiggle pattern.

Problem Example: Consider nums = [4, 5, 5, 6]:

• Sorted: [4, 5, 5, 6]
• Using a naive approach might produce: [5, 6, 4, 5]
• This violates the pattern at indices 2-3: 4 < 5 but we need 4 > 5

Why This Happens: When duplicate values exist near the median, they can end up in both the "smaller" and "larger" halves. The backward traversal strategy helps mitigate this by maximizing the distance between where duplicates are placed, but understanding this is crucial.

Solution: Understanding the Backward Traversal Strategy

The algorithm deliberately traverses both halves backward to create maximum separation between potential duplicate values:

def wiggleSort(self, nums: List[int]) -> None:
    sorted_array = sorted(nums)
    n = len(sorted_array)
  
    # Key insight: Start from the rightmost elements of each half
    # This maximizes distance between duplicates
    mid = (n - 1) // 2  # Last index of smaller half
    end = n - 1         # Last index of larger half
  
    # Fill the array alternating between halves, going backward
    for i in range(n):
        if i % 2 == 0:
            nums[i] = sorted_array[mid]
            mid -= 1
        else:
            nums[i] = sorted_array[end]
            end -= 1

Visual Example with Duplicates: For nums = [1, 1, 2, 2, 3, 3]:

• Sorted: [1, 1, 2, 2, 3, 3]
• Mid pointer starts at index 2 (value 2)
• End pointer starts at index 5 (value 3)
• Result: [2, 3, 1, 3, 1, 2] ✓ (satisfies wiggle pattern)

If we had used forward traversal instead:

• Would produce: [1, 2, 1, 2, 2, 3] ✗ (fails at indices 3-4: 2 = 2)

Additional Considerations:

1. Array Length: The algorithm works correctly for both even and odd length arrays due to the (n-1)//2 calculation for the middle index.

2. Edge Case - All Same Elements: While the problem guarantees a valid answer exists, arrays with all identical elements (like [5, 5, 5, 5]) cannot form a valid wiggle pattern. The problem statement ensures this won't occur.

3. Alternative O(n) Solution: For those seeking optimal time complexity, there exists a more complex O(n) solution using virtual indexing and three-way partitioning (Dutch National Flag algorithm variant), but it's significantly harder to implement and understand.