Wiggle Sort II
Medium · Arrays & Hashing · Array · Divide and Conquer · Greedy · Sorting · Quickselect
Problem
You are given an integer array nums. Reorder it in place so that nums[0] nums[2] ..., with strict inequalities everywhere.
The input always has at least one valid arrangement, and any valid arrangement is accepted.
Examples
Input: nums = [2,5,1,4,3,3] Output: [3,5,2,4,1,3]
3 2 1 < 3. Other valid orders are accepted too.
Input: nums = [1,1,2,2,3,3] Output: [2,3,1,3,1,2]
Filling each half from its largest value keeps the two 2s apart: 2 1 1 < 2.
Input: nums = [4,5,5,6] Output: [5,6,4,5]
5 4 < 5: one 5 opens the array and the other closes it.
Constraints
- 1 <= len(nums) <= 5 · 10^4
- 0 <= nums[i] <= 5000
- A valid answer is guaranteed to exist
Approaches
- Baseline: insertion sort, then interleave — time O(n²), space O(n)
Follow-up
With = allowed, a single pass that swaps each wrongly ordered neighbor pair is enough, and no sorting is needed. The strict version needs the median because the only way two equal values can be forced next to each other is when that value is the median.
Related problems
Start free on Cariara · Coding problems · System design studio
