[Medium] 324. Wiggle Sort II

Rearrange nums such that nums[0] < nums[1] > nums[2] < nums[3] ... (wiggle order).

Examples

Example:

Input: nums = [1,5,1,1,6,4]
Output: [1,6,1,5,1,4]
Explanation: 1 < 6 > 1 < 5 > 1 < 4

Constraints

  • 1 <= nums.length <= 5 * 10^4
  • 0 <= nums[i] <= 5000

Clarification Questions

Before diving into the solution, here are 5 important clarifications and assumptions to discuss during an interview:

  1. Wiggle sort definition: What is wiggle sort? (Assumption: nums[0] < nums[1] > nums[2] < nums[3] > … - alternating less than and greater than)

  2. Sorting requirement: Should we sort in-place? (Assumption: Yes - modify array in-place, O(1) extra space)

  3. Return value: What should we return? (Assumption: Void - modify array in-place)

  4. Uniqueness: Can values be equal? (Assumption: Per constraints, values can be equal, but wiggle pattern requires strict inequality)

  5. Time complexity: What time complexity is expected? (Assumption: O(n) average using nth_element and virtual indexing)

Interview Deduction Process (20 minutes)

Step 1: Brute-Force Approach (5 minutes)

Sort the array, then rearrange elements: place larger half in odd positions and smaller half in even positions. However, this may not satisfy the strict inequality requirement (nums[0] < nums[1] > nums[2] < nums[3]…). Need to handle duplicates carefully to avoid equal adjacent elements.

Step 2: Semi-Optimized Approach (7 minutes)

Sort the array and use two pointers: one starting from middle, one from end. Interleave elements: place smaller elements at even indices and larger elements at odd indices. However, with duplicates, we need to ensure strict inequalities. May need to reverse one half or use a more sophisticated interleaving strategy.

Step 3: Optimized Solution (8 minutes)

Use three-way partition (similar to Dutch National Flag) to find the median, then use virtual indexing to place elements. Alternatively, sort the array, then interleave by placing larger half in reverse order at odd indices and smaller half in reverse order at even indices. The key insight is that by reversing one half, we ensure that adjacent elements from the same half are separated, maintaining the wiggle property. This achieves O(n log n) time for sorting plus O(n) for rearrangement, which is optimal for the general case. For O(n) time, use quickselect to find median, then three-way partition with virtual indexing.

Solution: Median + 3-way Partition with Virtual Indexing

Time Complexity: O(n) average (due to nth_element)
Space Complexity: O(1) extra

Steps:

  • Find the median in-place using nth_element (average O(n))
  • Use a 3-way partition (Dutch National Flag) around the median
  • Apply a virtual index mapping vi(i) = (1 + 2*i) % (n | 1) so that larger numbers go to odd indices and smaller ones to even indices, achieving wiggle order
class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        const int n = nums.size();
        auto midIt = nums.begin() + n / 2;
        nth_element(nums.begin(), midIt, nums.end());
        int median = *midIt;

        auto vi = [n](int i) {return (1 + 2 * i) % (n | 1);};
        int left = 0, right = n - 1, i = 0;
        while(i <= right) {
            if(nums[vi(i)] > median) {
                swap(nums[vi(left)], nums[vi(i)]);
                left++;
                i++;
            } else if(nums[vi(i)] < median) {
                swap(nums[vi(i)], nums[vi(right)]);
                right--;
            } else {
                i++;
            }
        }
    }
};

Why Virtual Indexing Works

  • The mapping vi(i) = (1 + 2*i) % (n | 1) interleaves indices so that large elements are placed at positions 1, 3, 5, … and small elements at 0, 2, 4, …
  • Partitioning by median ensures elements greater than median occupy odd positions, and elements less than median occupy even positions, satisfying wiggle constraints.

Key Insights

  • nth_element finds the median in average O(n) time
  • 3-way partition handles duplicates correctly
  • Virtual indexing avoids overwriting placements by distributing indices across the array cyclically

Edge Cases

  • All elements equal → already wiggle (no swaps needed)
  • Many duplicates → 3-way partition around median is essential
  • Small arrays (n <= 2) → already satisfy or trivially adjustable
  • [280. Wiggle Sort] — simpler version without strict inequality
  • [75. Sort Colors] — Dutch National Flag
  • [215. Kth Largest Element in an Array] — nth_element