#324 Wiggle Sort II

Mediumsolve on LeetCode ↗

frequently reported atGoogle Amazon

the problem

In plain words

Reorder nums so that nums[0] < nums[1] > nums[2] < nums[3] … A valid answer always exists.

in nums = [1,5,1,1,6,4]

out [1,6,1,5,1,4]

Other wiggles are accepted too.

in nums = [1,3,2,2,3,1]

out [2,3,1,3,1,2]

1 ≤ n ≤ 5·10⁴
0 ≤ nums[i] ≤ 5000

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternCounting / bucket sort Quickselect

Put the smaller half on even slots and the larger half on odd slots, both in descending order — that pushes copies of the median as far apart as possible so they never touch.

solutions

From brute force to optimal

Sorted copy; even slots take the small half from its end, odd slots the large half from its end.

s = sorted copy.
small = (n+1)/2 − 1, large = n − 1.
nums[i] = i even ? s[small--] : s[large--].

timeO(n log n)

Sorting.

spaceO(n)

The sorted copy.

javajava.util.*

1class Solution {2    public void wiggleSort(int[] nums) {3        int[] s = nums.clone();4        Arrays.sort(s);5        int n = nums.length;6        int small = (n + 1) / 2 - 1;  // last index of the smaller half7        int large = n - 1;            // last index of the larger half8        for (int i = 0; i < n; i++) {9            // Even slots take the smaller half, odd slots the larger half — both from the END,10            // so equal middle values land as far apart as possible.11            nums[i] = (i % 2 == 0) ? s[small--] : s[large--];12        }13    }14}

Values ≤ 5000: fill odd slots with the largest values, then even slots, both descending.

Count values.
Walk values high → low filling indices 1, 3, 5, …
Continue filling 0, 2, 4, …

timeO(n + R)

R = 5001 possible values.

spaceO(R)

The count array (no copy of nums).

javajava.util.*

1class Solution {2    public void wiggleSort(int[] nums) {3        int[] count = new int[5001];               // constraint: 0 ≤ nums[i] ≤ 50004        for (int x : nums) count[x]++;5        int v = 5000;6        for (int i = 1; i < nums.length; i += 2) { // odd slots get the largest values7            while (count[v] == 0) v--;8            nums[i] = v;9            count[v]--;10        }11        for (int i = 0; i < nums.length; i += 2) { // even slots get what's left, still descending12            while (count[v] == 0) v--;13            nums[i] = v;14            count[v]--;15        }16    }17}

Quickselect the median, then Dutch-flag partition on the index order 1, 3, 5, …, 0, 2, 4, … so big values land on odd slots.

median = quickselect(n/2).
map(i) = (1 + 2i) % (n | 1) visits odd slots first, then even.
3-way partition through map: > median to the front of the virtual order, < median to the back.

timeO(n) average

Quickselect is O(n) expected; the partition is one pass.

spaceO(1)

In place — this answers the follow-up.

javajava.util.*

1class Solution {2    private final Random rnd = new Random();3 4    public void wiggleSort(int[] nums) {5        int n = nums.length;6        int median = select(nums, n / 2);   // expected O(n); reordering nums is fine, we rearrange it next7        // Dutch flag on "virtual" indices 1, 3, 5, ..., 0, 2, 4, ...:8        // bigger-than-median values go to odd slots first, smaller ones to the even slots at the end.9        int left = 0, i = 0, right = n - 1;10        while (i <= right) {11            if (nums[map(i, n)] > median) swap(nums, map(left++, n), map(i++, n));12            else if (nums[map(i, n)] < median) swap(nums, map(right--, n), map(i, n));13            else i++;14        }15    }16 17    private int map(int i, int n) {18        return (1 + 2 * i) % (n | 1);               // 0→1, 1→3, ... wraps to 0, 2, 4, ...19    }20 21    private int select(int[] a, int k) {           // k-th smallest, 0-based22        int lo = 0, hi = a.length - 1;23        while (true) {24            int pivot = a[lo + rnd.nextInt(hi - lo + 1)];25            int lt = lo, i = lo, gt = hi;26            while (i <= gt) {27                if (a[i] < pivot) swap(a, lt++, i++);28                else if (a[i] > pivot) swap(a, i, gt--);29                else i++;30            }31            if (k < lt) hi = lt - 1;32            else if (k > gt) lo = gt + 1;33            else return pivot;34        }35    }36 37    private void swap(int[] a, int i, int j) {38        int t = a[i]; a[i] = a[j]; a[j] = t;39    }40}

in the room

How to say it in the interview

talk track

Show why naive interleaving (small half ascending) fails on [4,5,5,6] → [4,5,5,6] has 5 next to 5.
Lead with sort + reverse interleave; mention the O(n)/O(1) virtual-index trick as the follow-up.

traps

Filling halves in ascending order — equal medians end up adjacent.

what they ask next

Follow-ups

Wiggle Sort I (LC 280) with ≤ / ≥?

One greedy pass: swap nums[i] with nums[i−1] whenever the pair breaks the pattern — O(n).

before you submit

Edge cases to test

One element: already a wiggle.
[4, 5, 5, 6]: ascending halves give 4 5 5 6 (5 next to 5); descending halves give 5 6 4 5.
Many copies of the median, like [1, 1, 2, 2, 2, 3, 3]: the reverse interleave still keeps them apart.

practise next