The O(n) Club: Wiggle Sort II: The Interview Pattern That Spoils Dev Confidence

The O(n) Club: Wiggle Sort II — The Interview Pattern That Spoils Dev Confidence

⚡ TL;DR

If you still think Wiggle Sort II is just another sorting problem, welcome to a world of pain. This beast is about where you put things, not how you line them up. Sort the numbers, then fill even indexes with the smaller half (from the end, of course) and odd with the bigger ones. Duplicates? Banished! Here’s the classic Java move:

// O(n log n) Wiggle Sort II
void wiggleSort(int[] nums) {
    int n = nums.length;
    int[] sorted = Arrays.copyOf(nums, n);
    Arrays.sort(sorted);
    int mid = (n - 1) / 2, end = n - 1;
    for (int i = 0; i < n; ++i)
        nums[i] = (i % 2 == 0) ? sorted[mid--] : sorted[end--];
}

🧠 How Devs Usually Mess This Up

Most devs bravely run forward, alternating sorted values like a robot at a bread factory. Except, when duplicates show up, the code falls apart. Try [1, 1, 2, 2, 3, 3] → [1, 2, 1, 2, 2, 3]. See those two 2’s cuddling up? Yeah, try explaining that to your interviewer. Forward placement with duplicates is basically an RSVP to pain.

🔍 What’s Actually Going On

This problem isn’t sorting, it’s social distancing—but for numbers. Like seating rowdy twins apart at a family reunion, you want to shove identical numbers far from each other. The trick? After sorting, distribute values backwards: even slots for the smallest (from the middle), odd slots for the biggest. Duplicates can’t clump, so the wiggle naturally appears. It’s algorithmic crowd control, minus the whistle.

🛠️ PseudoCode

• Sort the input array. (Like cleaning your kitchen before you cook—necessary, not glamorous)
• Copy the sorted values so you don’t step on your own toes while rearranging.
• Set two pointers:
  • mid: last index of the smaller half
  • end: last index overall
• Reassign every index:
  • If i is even, grab from mid and walk backwards.
  • If i is odd, take from end and—yes—walk backwards.

// pseudocode
Arrays.sort(nums);
int mid = (n-1)/2, end = n-1;
for (i = 0; i < n; ++i)
    nums[i] = (i is even) ? sorted[mid--] : sorted[end--];

💻 The Code

import java.util.Arrays;
 public class WiggleSortII {
    public void wiggleSort(int[] nums) {
        int n = nums.length;
        int[] sorted = Arrays.copyOf(nums, n);
        Arrays.sort(sorted);
        int mid = (n - 1) / 2;
        int end = n - 1;
        for (int i = 0; i < n; ++i)
            nums[i] = (i % 2 == 0) ? sorted[mid--] : sorted[end--];
    }
     public static void main(String[] args) {
        int[] nums = {1, 3, 2, 2, 3, 1};
        new WiggleSortII().wiggleSort(nums);
        System.out.println(Arrays.toString(nums));
        // Output example: [2, 3, 1, 3, 1, 2]
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Even vs Odd: Watch where mid lands. One off, duplicates party together.
• Not in-place: Requires an extra O(n) array. Sorry, neat freaks—unless you use the scary O(n) quickselect + virtual index.
• Forward == Fail: Seriously. Forward distribution lets duplicates clump faster than pizza on office free food day.
• Time: O(n log n) for the sort, O(n) for the rest. You’ll live.

🧠 Interviewer Brain-Tattoo

“Next time you see alternating patterns, skip the sort-flex and just keep the copycats apart. Your arrays—and your interviewer—will thank you.”