Wiggle Sort II - Solution & Explanation

Problem Overview: Wiggle Sort II asks you to reorder an array so that nums[0] < nums[1] > nums[2] < nums[3].... The tricky part is handling duplicates while keeping the strict wiggle pattern. A naive rearrangement often breaks when many values are equal, so the solution needs careful placement of small and large elements.

Approach 1: Sort and Merge (O(n log n) time, O(n) space)

The simplest strategy is to sort the array and then interleave the two halves. After sorting, split the array around the median. Place the smaller half in reverse order at even indices and the larger half in reverse order at odd indices. Reversing both halves ensures duplicates don't sit next to each other and break the wiggle condition. This approach relies on sorting and simple array iteration, making it easy to implement in interviews when optimal performance is not required.

Steps: sort the array, compute the midpoint, then iterate through the result array filling even indices from the end of the first half and odd indices from the end of the second half. Time complexity is O(n log n) due to sorting, and extra space O(n) if using a temporary array.

Approach 2: Tri-Partition with Virtual Indexing (O(n) time, O(1) space)

The optimal solution uses a combination of Quickselect and a three-way partition similar to the Dutch National Flag algorithm. First, find the median of the array in O(n) average time using Quickselect. The median becomes the pivot that separates smaller and larger values.

Instead of rearranging elements directly, apply virtual indexing. Map each logical position i to (1 + 2*i) % (n | 1). This mapping places larger elements in odd indices and smaller elements in even indices automatically. Then perform a three-way partition: elements greater than the median move to the front of the virtual order, elements smaller move to the back, and median values stay in the middle.

This technique ensures the final arrangement satisfies nums[0] < nums[1] > nums[2] < nums[3] even when many elements equal the median. The algorithm runs in O(n) time with O(1) extra space and heavily uses concepts from array manipulation and partition-based algorithms.

Recommended for interviews: Start with the sorting-based solution because it demonstrates clear reasoning and is easy to verify. Interviewers usually push for the optimal solution afterward. The Quickselect + virtual indexing method shows deeper understanding of partitioning, index mapping, and in-place algorithms, which is the solution expected at top companies.