hard

Wiggle Sort II

Rearrange an array in place so it alternates strictly between smaller and larger values.

1. Define the problem

Wiggle Sort II

Given an integer array nums, reorder it in place so that nums0 < nums1 > nums2 < nums3 ... — every element strictly alternates between smaller and greater than its neighbors. You may assume a valid wiggle arrangement always exists for the input, and any valid arrangement is accepted. Find the median in O(n) average time with quickselect , then partition the array into values above, equal to, and below it, placing the larger half at alternating positions.

Constraints

  • 1 ≤ nums.length ≤ 5 × 104
  • 0 ≤ numsi ≤ 5000
  • It is guaranteed that there is a valid answer for the given input

Example

Inputnums = [1, 5, 1, 1, 6, 4]
Output[1, 5, 1, 4, 1, 6]

Explanation Multiple valid wiggle arrangements exist for this input; this is the one produced by finding the median (1) with quickselect and partitioning around it. Check it alternates: 1 < 5 > 1 < 4 > 1 < 6.

2. Know the words first

In plain terms

Median
The middle value of a sorted array — half the values are less than or equal to it, half are greater than or equal to it.
3. Visualize the solution

Find the median, then partition around it into alternating positions

Find the median, then partition around it into alternating positions
Statusmedian = 1

Quickselect found the median (1) in O(n) average time. Now partition the array around it.

What happens in this step

nums = [1, 1, 2, 2] (simplified 4-element example)
sortedCopy = [1, 1, 2, 2]
median = quickSelect(sortedCopy, k = floor((4-1)/2) = 1) = 1

n=4 is even, so n | 1 = 5 and mapIndex(i) = (2i + 1) % 5 walks alternating positions from both ends inward: mapIndex(0)=1, mapIndex(1)=3, mapIndex(2)=0, mapIndex(3)=2.
left=0, mid=0, right=3 — ready to partition nums around the median using that index mapping.
Step 1 of 4

Steps to visualize

  1. Run quickselect on a copy of the array to find its median value in O(n) average time.
  2. Walk through the original array once, comparing each value to the median.
  3. Values greater than the median move toward the even (0-indexed) positions from the outside in.
  4. Values less than the median move toward the odd positions from the outside in.
  5. Values equal to the median stay put — the alternating placement guarantees no two equal values end up adjacent.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Find the median, then partition around it into alternating positions
Statusmedian = 1

Quickselect found the median (1) in O(n) average time. Now partition the array around it.

What happens in this step

nums = [1, 1, 2, 2] (simplified 4-element example)
sortedCopy = [1, 1, 2, 2]
median = quickSelect(sortedCopy, k = floor((4-1)/2) = 1) = 1

n=4 is even, so n | 1 = 5 and mapIndex(i) = (2i + 1) % 5 walks alternating positions from both ends inward: mapIndex(0)=1, mapIndex(1)=3, mapIndex(2)=0, mapIndex(3)=2.
left=0, mid=0, right=3 — ready to partition nums around the median using that index mapping.
Step 1 of 4
5. Solution

Solution

solution.tsTypeScript
function wiggleSort(nums) {
  const n = nums.length;

  function partition(arr, lo, hi) {
    const pivot = arr[hi];
    let i = lo;

    for (let j = lo; j < hi; j++) {
      if (arr[j] < pivot) {
        [arr[i], arr[j]] = [arr[j], arr[i]];
        i++;
      }
    }

    [arr[i], arr[hi]] = [arr[hi], arr[i]];
    return i;
  }

  function quickSelect(arr, k) {
    let lo = 0;
    let hi = arr.length - 1;

    while (lo < hi) {
      const pivotIndex = partition(arr, lo, hi);
      if (pivotIndex === k) break;
      if (pivotIndex < k) lo = pivotIndex + 1;
      else hi = pivotIndex - 1;
    }

    return arr[k];
  }

  const sortedCopy = nums.slice();
  const median = quickSelect(sortedCopy, Math.floor((n - 1) / 2));

  const mapIndex = (i) => (2 * i + 1) % (n | 1);

  let left = 0;
  let mid = 0;
  let right = n - 1;

  while (mid <= right) {
    const midValue = nums[mapIndex(mid)];

    if (midValue > median) {
      const li = mapIndex(left);
      const mi = mapIndex(mid);
      [nums[li], nums[mi]] = [nums[mi], nums[li]];
      left++;
      mid++;
    } else if (midValue < median) {
      const mi = mapIndex(mid);
      const ri = mapIndex(right);
      [nums[mi], nums[ri]] = [nums[ri], nums[mi]];
      right--;
    } else {
      mid++;
    }
  }

  return nums;
}
Time
O(n) average, O(n²) worst case, for the median quickselect plus an O(n) partition
Space
O(n) for the sorted copy used to find the median
6. Test cases

Test cases

InputExpectedCovers
nums = [1, 5, 1, 1, 6, 4][1, 5, 1, 4, 1, 6]example from the docstring, with duplicate values
nums = [1, 3, 2, 2, 3, 1][2, 3, 1, 3, 1, 2]even length with several repeated values around the median
nums = [5][5]smallest valid input, a single element trivially satisfies the wiggle property
nums = [2, 1][1, 2]boundary case, exactly two elements
nums = [4, 2, 3][3, 4, 2]odd length array, a true single median value
nums = [1, 1, 2, 2][1, 2, 1, 2]even length with only two distinct values, the classic adjacent-duplicate trap

Keep reading