Wiggle Sort II
Problem
Reorder nums in place so that nums[0] < nums[1] > nums[2] < nums[3] > … (strictly).
nums = [1, 5, 1, 1, 6, 4][1, 6, 1, 5, 1, 4]def wiggle_sort(nums):
s = sorted(nums)
n = len(nums)
half = (n + 1) // 2
# smaller half (reversed) → even indices; larger half (reversed) → odd indices
nums[0::2] = s[:half][::-1]
nums[1::2] = s[half:][::-1]
return numsfunction wiggleSort(nums) {
const s = [...nums].sort((a, b) => a - b);
const n = nums.length;
const half = (n + 1) >> 1;
for (let i = 0, j = half - 1; i < n; i += 2, j--) nums[i] = s[j];
for (let i = 1, j = n - 1; i < n; i += 2, j--) nums[i] = s[j];
return nums;
}class Solution {
public void wiggleSort(int[] nums) {
int[] s = nums.clone();
Arrays.sort(s);
int n = nums.length, half = (n + 1) / 2;
for (int i = 0, j = half - 1; i < n; i += 2, j--) nums[i] = s[j];
for (int i = 1, j = n - 1; i < n; i += 2, j--) nums[i] = s[j];
}
}void wiggleSort(vector<int>& nums) {
vector<int> s = nums;
sort(s.begin(), s.end());
int n = nums.size(), half = (n + 1) / 2;
for (int i = 0, j = half - 1; i < n; i += 2, j--) nums[i] = s[j];
for (int i = 1, j = n - 1; i < n; i += 2, j--) nums[i] = s[j];
}Explanation
We need a strict zig-zag: nums[0] < nums[1] > nums[2] < …. The safe recipe is to sort a copy, then interleave the smaller half into the even slots and the larger half into the odd slots.
After sorting, we split at half = (n + 1) // 2. The lower half (small numbers) feeds the even indices 0, 2, 4…, and the upper half (big numbers) feeds the odd indices 1, 3, 5….
The crucial twist is filling both halves in reverse (largest of each half first). This pushes any duplicate values as far apart as possible, so equal numbers never land in neighboring valley/peak slots and break the strict inequality.
Example: [1,5,1,1,6,4] sorts to [1,1,1,4,5,6]. Lower half [1,1,1] reversed fills even slots, upper half [4,5,6] reversed fills odd slots, giving [1,6,1,5,1,4] which wiggles correctly.
It works because the smallest numbers only sit in valleys and the largest only in peaks, and the reverse ordering keeps the troublesome repeats from ever touching.