medium

Wiggle Sort

Reorder an array in place so it alternately rises and falls.

1. Define the problem

Wiggle Sort

Given an integer array nums, reorder it in place so that nums0 ≤ nums1 ≥ nums2 ≤ nums3 … alternates for the whole array. Unlike a stricter version of this problem, ties are allowed — equal neighboring values are perfectly fine. A single left-to-right sweep with one swap per broken pair is enough: at every even position check for "too big", and at every odd position check for "too small", swapping with the next element whenever the pattern is violated.

Constraints

  • 1 ≤ nums.length ≤ 5 × 104
  • 0 ≤ numsi ≤ 104
  • It is guaranteed that there will be an answer for the given input nums.

Example

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

Explanation One valid wiggle result: 3 ≤ 5 ≥ 1 ≤ 6 ≥ 2 ≤ 4. (Other orderings are also accepted on LeetCode; this walkthrough shows exactly what the one-pass swap approach below produces.)

2. Know the words first

In plain terms

Left-to-right sweep
Looking at each neighboring pair exactly once, in order, and fixing it immediately rather than re-scanning the whole array repeatedly.
3. Visualize the solution

Sweep left to right, swapping whenever the pattern breaks

Sweep left to right, swapping whenever the pattern breaks
Statusok

i=0 (even): nums[0]=3 is not greater than nums[1]=5 — no swap needed.

What happens in this step

i = 0 (even index)
nums[0] = 3, nums[1] = 5
3 > 5 is false, no swap
Step 1 of 5

Steps to visualize

  1. At every even index, the value there should be less than or equal to its neighbor — if it is greater, swap them.
  2. At every odd index, the value there should be greater than or equal to its neighbor — if it is smaller, swap them.
  3. Move to the next index and repeat, one comparison at a time, never looking back.
  4. By the time the sweep reaches the end, every adjacent pair satisfies the alternating pattern.
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.

Sweep left to right, swapping whenever the pattern breaks
Statusok

i=0 (even): nums[0]=3 is not greater than nums[1]=5 — no swap needed.

What happens in this step

i = 0 (even index)
nums[0] = 3, nums[1] = 5
3 > 5 is false, no swap
Step 1 of 5
5. Solution

Solution

solution.tsTypeScript
function wiggleSort(nums) {
  for (let i = 0; i < nums.length - 1; i++) {
    const isEvenIndex = i % 2 === 0;

    if (isEvenIndex && nums[i] > nums[i + 1]) {
      [nums[i], nums[i + 1]] = [nums[i + 1], nums[i]];
    } else if (!isEvenIndex && nums[i] < nums[i + 1]) {
      [nums[i], nums[i + 1]] = [nums[i + 1], nums[i]];
    }
  }

  return nums;
}
Time
O(n)
Space
O(1)
6. Test cases

Test cases

InputExpectedCovers
nums = [3, 5, 2, 1, 6, 4][3, 5, 1, 6, 2, 4]example from the docstring
nums = [1, 2][1, 2]smallest valid input: only two elements, already in order
nums = [5][5]a single element trivially satisfies the pattern
nums = [1, 3, 2, 4][1, 3, 2, 4]an array that already satisfies the wiggle pattern
nums = [2, 2, 2, 2][2, 2, 2, 2]every value equal, which trivially satisfies the pattern with ties
nums = [4, 3, 2, 1][3, 4, 1, 2]a fully reverse-sorted array that needs swaps at every step

Keep reading