Code Implementation

class Solution:
    def wiggleSort(self, nums):
        n = len(nums)
        sorted_nums = sorted(nums)
        mid = (n + 1) // 2
        left = sorted_nums[:mid][::-1]
        right = sorted_nums[mid:][::-1]
        for i in range(n):
            if i % 2 == 0:
                nums[i] = left[i // 2]
            else:
                nums[i] = right[i // 2]
      

class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        int n = nums.size();
        vector<int> sorted(nums);
        sort(sorted.begin(), sorted.end());
        int mid = (n + 1) / 2;
        int left = mid - 1, right = n - 1;
        for (int i = 0; i < n; ++i) {
            if (i % 2 == 0)
                nums[i] = sorted[left--];
            else
                nums[i] = sorted[right--];
        }
    }
};
      

class Solution {
    public void wiggleSort(int[] nums) {
        int n = nums.length;
        int[] sorted = nums.clone();
        Arrays.sort(sorted);
        int mid = (n + 1) / 2;
        int left = mid - 1, right = n - 1;
        for (int i = 0; i < n; ++i) {
            if (i % 2 == 0)
                nums[i] = sorted[left--];
            else
                nums[i] = sorted[right--];
        }
    }
}
      

var wiggleSort = function(nums) {
    let n = nums.length;
    let sorted = [...nums].sort((a, b) => a - b);
    let mid = Math.floor((n + 1) / 2);
    let left = sorted.slice(0, mid).reverse();
    let right = sorted.slice(mid).reverse();
    for (let i = 0; i < n; ++i) {
        nums[i] = (i % 2 === 0) ? left[Math.floor(i / 2)] : right[Math.floor(i / 2)];
    }
};
      

Problem Description

Given an unsorted array of integers nums, rearrange the elements in-place to satisfy the following "wiggle" property:
nums[0] < nums[1] > nums[2] < nums[3] > nums[4] ...
In other words, every odd-indexed element should be greater than its neighbors, and every even-indexed element should be less than its neighbors.
Constraints:

• You must do this in-place (modify nums).
• There is at least one valid solution for any input.
• Each element must appear exactly once (no duplicates or omissions).

Thought Process

At first glance, the problem seems similar to sorting, but with a twist: the numbers must alternate between "less than" and "greater than" their neighbors. One might think about generating all possible permutations and checking which ones satisfy the wiggle condition, but this is highly inefficient for large arrays.

A more systematic approach involves sorting the array to get the order of values, then distributing the largest and smallest elements in such a way that the wiggle property is preserved. The main idea is to ensure that the largest available numbers occupy the odd indices (peaks), and the smaller numbers fill the even indices (valleys).

This leads us to think about splitting the sorted array in half and interleaving the two halves in reverse order, ensuring the wiggle pattern is preserved. The challenge is to do this efficiently and in-place, without using extra space if possible.

Solution Approach

Let's break down the steps to solve the problem efficiently:

1. Sort the array: Start by sorting a copy of nums. This allows us to easily access the smallest and largest elements.
2. Split the sorted array: Divide the sorted array into two halves. The first half contains the smaller elements, and the second half contains the larger elements.
3. Reverse both halves: Reverse both halves to start placing the largest available numbers first. This prevents equal numbers from being adjacent when the halves are interleaved.
4. Interleave the halves: Place elements from the reversed first half at even indices (0, 2, 4, ...), and elements from the reversed second half at odd indices (1, 3, 5, ...).
5. In-place update: Assign the values directly back into nums to satisfy the in-place requirement.

• By always placing the next largest remaining element at odd indices, we ensure each "peak" is as high as possible.
• Placing the next largest of the smaller half at even indices ensures "valleys" are as low as possible.
• Reversing each half avoids placing duplicate values next to each other, which could break the wiggle condition.

Example Walkthrough

Let's use the sample input nums = [1, 5, 1, 1, 6, 4].
Step 1: Sort the array: [1, 1, 1, 4, 5, 6]
Step 2: Split into halves:

• First half (smaller): [1, 1, 1]
• Second half (larger): [4, 5, 6]

• Left (first half reversed): [1, 1, 1]
• Right (second half reversed): [6, 5, 4]

• Index 0 (even): left[0] = 1
• Index 1 (odd): right[0] = 6
• Index 2 (even): left[1] = 1
• Index 3 (odd): right[1] = 5
• Index 4 (even): left[2] = 1
• Index 5 (odd): right[2] = 4

Time and Space Complexity

Brute-force approach:

• Would involve generating all permutations and checking each for the wiggle property.
• Time complexity: O(n!) — impractical for large n.
• Space complexity: O(n) for recursion stack or storing permutations.

• Sorting the array: O(n log n)
• Splitting and reversing: O(n)
• Interleaving: O(n)
• Total time complexity: O(n log n)
• Space complexity: O(n) for the sorted copy and splits.
• In-place variants exist using index mapping, but are more complex and less intuitive for beginners.

Summary

Wiggle Sort II asks us to rearrange an array so that it alternates between valleys and peaks. The most efficient and clear solution involves sorting the array, splitting it into two halves, reversing both, and interleaving the values to ensure the wiggle property holds. This approach is elegant because it leverages sorting to organize values, and simple index logic to distribute them correctly. The result is an O(n log n) time, O(n) space solution that is both easy to implement and understand.