276. Wiggle Sort II
Rearrange the integer array nums so its values strictly alternate low–high: nums[0] < nums[1] > nums[2] < nums[3] > …. Every input is guaranteed to admit at least one such arrangement.
Since many wiggle arrangements can exist, return the canonical one, built exactly like this:
- Sort the values ascending.
- Split into a low half — the first
⌈n/2⌉values (the low half takes the extra element whennis odd) — and a high half, the rest. - Place the low half into the even indices
0, 2, 4, …in reverse (descending) order, and the high half into the odd indices1, 3, 5, …in reverse order.
Your function receives nums and returns the rearranged array. This construction is always a valid wiggle whenever one exists — and it is the one arrangement the judge accepts.
Example 1:
Input: nums = [1, 5, 1, 1, 6, 4]
Output: [1, 6, 1, 5, 1, 4]
Explanation: Sorted: [1, 1, 1, 4, 5, 6]. Low half [1, 1, 1] reversed fills indices 0, 2, 4; high half [4, 5, 6] reversed fills indices 1, 3, 5 as 6, 5, 4. Check: 1 < 6 > 1 < 5 > 1 < 4.
Example 2:
Input: nums = [1, 3, 2, 2, 3, 1]
Output: [2, 3, 1, 3, 1, 2]
Explanation: Sorted: [1, 1, 2, 2, 3, 3]. Low half [1, 1, 2] reversed gives 2, 1, 1 at the even indices; high half [2, 3, 3] reversed gives 3, 3, 2 at the odd ones. Check: 2 < 3 > 1 < 3 > 1 < 2.
Constraints:
- 1 ≤ nums.length ≤ 5 * 10⁴
- 0 ≤ nums[i] ≤ 5000
- The input is guaranteed to have at least one valid wiggle arrangement.
Hints:
Sort first. Dealing the low half into even slots and the high half into odd slots left-to-right seems right — but duplicates near the split collide. Try it on [4, 5, 5, 6].
Deal each half in reverse: fill slots 0, 2, 4, … from the low half's largest value down, and slots 1, 3, 5, … from the high half's largest down. The tied values around the split land as far apart as possible.
Values are at most 5000, so a counting sort replaces the comparison sort: deal straight out of the counts from the top — the largest ⌊n/2⌋ values fill the odd slots in order, the remaining values then fill the even slots.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [1, 5, 1, 1, 6, 4]
Expected output: [1, 6, 1, 5, 1, 4]