Wiggle Sort II — O(n) Virtual Index Rearrangement [LC 324]

Problem Statement#

Given an integer array nums, reorder it in-place so nums[0] < nums[1] > nums[2] < nums[3]... (wiggle sort where odd indices are greater than their neighbors).

Constraints:

• 1 <= nums.length <= 5 * 10^4
• 0 <= nums[i] <= 4999
• It is guaranteed that a wiggle sort arrangement exists

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

Input:  nums = [1,3,2,2,3,1]
Output: [2,3,1,3,1,2]

Why This Problem Matters#

LeetCode 324 is one of the harder "medium" problems — the naive sort-and-interleave approach fails for arrays with many duplicates. Google and Amazon use it to test whether candidates can identify why a simple approach breaks and construct a more careful one.

The subtle difficulty: if you just sort and interleave halves naively, equal elements from the two halves can end up adjacent. The fix requires placing larger elements at odd indices and smaller elements at even indices using a virtual index mapping, combined with finding the median in O(n) via quickselect.

The Core Insight#

Two-step approach:

1. Find the median of the array in O(n) using nth_element (quickselect)
2. Use a virtual index A(i) = (1 + 2*i) % (n | 1) that maps positions to interleaved odd-then-even indices
3. Three-way partition (Dutch National Flag) around the median using this virtual index

Why virtual indexing? Standard sort-and-interleave fails when there are many median elements — they end up placed at adjacent positions. The virtual index places larger elements in odd positions (index 1, 3, 5, ...) and smaller elements in even positions (index 0, 2, 4, ...) by accessing the array in that interleaved order.

Simpler O(n log n) approach: Sort, split into two halves, interleave from the back of each half. This works and is much easier to explain in an interview.

Visual Dry Run#

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

Sort: [1, 1, 1, 4, 5, 6] Lower half (from back): [1, 1, 1] — place at even indices (0, 2, 4) Upper half (from back): [6, 5, 4] — place at odd indices (1, 3, 5)

Interleaved: [1, 6, 1, 5, 1, 4]

Check: 1<6>1<5>1<4 — valid wiggle!

Solution (Optimal)#

class Solution:
    def wiggleSort(self, nums):
        # Simpler O(n log n) approach using sort + interleave from back
        n = len(nums)
        arr = sorted(nums)
        # Upper half (larger) fills odd indices from right to left
        # Lower half (smaller) fills even indices from right to left
        j = n - 1          # pointer into upper half
        k = (n - 1) // 2  # pointer into lower half (end of lower half)
        for i in range(1, n, 2):   # odd indices first
            nums[i] = arr[j]
            j -= 1
        for i in range(0, n, 2):   # even indices
            nums[i] = arr[k]
            k -= 1

var wiggleSort = function(nums) {
    const arr = [...nums].sort((a, b) => a - b);
    const n = nums.length;
    let j = n - 1;
    let k = Math.floor((n - 1) / 2);
    for (let i = 1; i < n; i += 2) {
        nums[i] = arr[j--];
    }
    for (let i = 0; i < n; i += 2) {
        nums[i] = arr[k--];
    }
};

Time: O(n log n) — sorting dominates Space: O(n) — copy of sorted array

Common Mistakes#

• Naive sort-and-interleave from the front — fails when many elements equal the median (creates adjacent duplicates)
• Filling even positions from the start of the sorted array instead of the end of the lower half — causes equal elements to be adjacent
• Confusing this with Wiggle Sort I (LC 280) — LC 280 is one swap per step, LC 324 requires careful median-based placement
• Off-by-one in splitting into halves — lower half is indices 0..(n-1)//2, upper half is (n-1)//2+1..n-1
• Not filling odd indices before even indices — must place larger elements at odd positions first

Interview Tips#

• Start with the simpler O(n log n) approach and explain it clearly — most interviewers accept this
• Explain why filling from the back of each half prevents adjacent equal elements (duplicates end up separated)
• Draw the sorted array, show the two halves, and trace the interleaving step by step
• Mention the O(n) approach (nth_element + virtual indexing) only if asked for optimal complexity
• Wiggle Sort I vs II: LC 280 only requires nums[0] <= nums[1] >= nums[2] (not strictly), LC 324 requires strictly alternating

Follow-up Questions#

• What is the O(n) time, O(1) space approach? (nth_element to find median, then three-way partition with virtual index mapping (1+2*i)%(n|1))
• How does Wiggle Sort II differ from Wiggle Sort I (LC 280)? (LC 280 uses one swap per step in O(n), LC 324 needs stricter inequality)
• Why does filling from the back of each half prevent adjacent duplicates? (Elements equal to the median end up in the middle of each half; filling from back ensures they are separated by elements from the other side)
• Can this be done in-place without extra space (besides O(n) sort)? (Yes, with O(n) quickselect + three-way partition + virtual indexing)
• What if the input has all identical elements? (The problem guarantees a valid wiggle arrangement exists — if all equal, no valid wiggle exists)

Key Takeaways#

• LeetCode 324 is asked at Google and Amazon — the naive interleave approach fails for many duplicate values
• Key fix: fill even and odd positions from the back of their respective halves in the sorted array, not the front
• Filling from back prevents equal elements at the median boundary from landing at adjacent positions
• O(n log n) approach: sort, split into halves, interleave from back of each half using two separate loops
• O(n) approach: quickselect for median, then three-way partition with virtual index (1+2*i)%(n|1) — impressive but complex
• Always trace through a case with duplicates to verify the approach during interviews
• Wiggle Sort I (LC 280) is much simpler — one-pass with one swap; LC 324 is substantially harder due to strict inequality