Code Implementation

class Solution:
    def wiggleSort(self, nums):
        nums.sort()
        half = (len(nums) + 1) // 2
        small = nums[:half][::-1]
        large = nums[half:][::-1]
        for i in range(len(nums)):
            if i % 2 == 0:
                nums[i] = small[i // 2]
            else:
                nums[i] = large[i // 2]
      

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

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

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

Problem Description

The Wiggle Sort problem asks you to reorder a given integer array nums so that it follows a specific pattern:
nums[0] < nums[1] > nums[2] < nums[3] > nums[4] ...
That is, every even-indexed element should be less than its next neighbor, and every odd-indexed element should be greater than its next neighbor (if one exists). You must rearrange the elements in place, using all original numbers exactly once, and there is at least one valid solution for every input.

• You cannot add or remove elements.
• Each element must be used exactly once.
• The solution should work for arrays with duplicate numbers.

Thought Process

The first idea that may come to mind is to try all possible permutations of the array and check if any of them satisfy the wiggle property. However, this brute-force approach is impractical because the number of permutations grows factorially with the array size.

Instead, we want a more efficient method. If we sort the array, we can try to interleave the smaller and larger halves to create the desired up-and-down pattern. By carefully choosing which elements go into even and odd positions, we can ensure the wiggle property is maintained. This shifts our thinking from "trying everything" to "systematically constructing a valid order."

Solution Approach

• Step 1: Sort the Array
  Sorting helps us easily separate the smaller and larger elements.
• Step 2: Split into Two Halves
  Divide the sorted array into two parts:
  • The smaller half (including the median if odd length)
  • The larger half (the remaining elements)
• Step 3: Reverse Both Halves
  We reverse each half so that when we assign elements, we use the largest possible value at each step, which helps avoid duplicates being adjacent.
• Step 4: Interleave the Halves
  Assign elements from the reversed small half to even indices (0, 2, 4, ...) and from the reversed large half to odd indices (1, 3, 5, ...).
• Step 5: In-place Assignment
  Overwrite the original array with this new arrangement.

This approach ensures that the wiggle property is maintained, even with duplicate elements, and does not require extra space beyond a copy of the sorted array.

Example Walkthrough

Let's take nums = [1, 5, 1, 1, 6, 4] as an example:

1. Sort: [1, 1, 1, 4, 5, 6]
2. Split:
   • Small half (first 3): [1, 1, 1]
   • Large half (last 3): [4, 5, 6]
3. Reverse both:
   • Small: [1, 1, 1]
   • Large: [6, 5, 4]
4. Interleave:
   • nums[0] = 1 (small[0])
   • nums[1] = 6 (large[0])
   • nums[2] = 1 (small[1])
   • nums[3] = 5 (large[1])
   • nums[4] = 1 (small[2])
   • nums[5] = 4 (large[2])
   Final array: [1, 6, 1, 5, 1, 4]
5. Check wiggle property:
   • 1 < 6 > 1 < 5 > 1 < 4

The result satisfies the wiggle condition at every position.

Time and Space Complexity

• Brute-force: O(n!) time, as it tries all permutations.
• Optimized Approach:
  • Sorting the array takes O(n log n) time.
  • Splitting and interleaving take O(n) time.
  • We use O(n) extra space for the sorted copy and halves.
• Overall:
  • Time Complexity: O(n log n)
  • Space Complexity: O(n)

This is a significant improvement over the brute-force approach and is efficient enough for large inputs.

Summary

The Wiggle Sort problem can be solved efficiently by sorting the array, splitting it into two halves, reversing them, and then interleaving the elements into even and odd positions. This strategy leverages the properties of sorted order and careful assignment to guarantee the wiggle pattern, even when duplicate values are present. The result is a simple, elegant, and efficient solution that avoids brute-force and works for all valid input arrays.