Wiggle Sort

medium array greedy sorting

Problem

Reorder the array so a[0] <= a[1] >= a[2] <= a[3] >= … in-place.

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

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

Alternates: 3≤5≥1≤6≥2≤4.

nums (comma-separated)

def wiggle_sort(nums):
    for i in range(1, len(nums)):
        if (i % 2 == 1 and nums[i] < nums[i-1]) or            (i % 2 == 0 and nums[i] > nums[i-1]):
            nums[i], nums[i-1] = nums[i-1], nums[i]
    return nums

function wiggleSort(nums) {
  for (let i = 1; i < nums.length; i++) {
    if ((i % 2 === 1 && nums[i] < nums[i-1]) ||
        (i % 2 === 0 && nums[i] > nums[i-1])) {
      [nums[i], nums[i-1]] = [nums[i-1], nums[i]];
    }
  }
  return nums;
}

class Solution {
    public void wiggleSort(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            if ((i % 2 == 1 && nums[i] < nums[i-1]) ||
                (i % 2 == 0 && nums[i] > nums[i-1])) {
                int t = nums[i]; nums[i] = nums[i-1]; nums[i-1] = t;
            }
        }
    }
}

void wiggleSort(vector& nums) {
    for (int i = 1; i < (int)nums.size(); i++) {
        if ((i % 2 == 1 && nums[i] < nums[i-1]) ||
            (i % 2 == 0 && nums[i] > nums[i-1])) {
            swap(nums[i], nums[i-1]);
        }
    }
}

Explanation

The goal is the relaxed wiggle a[0] <= a[1] >= a[2] <= …. Surprisingly, one greedy pass with local swaps fixes the whole array — no sorting needed.

We walk from i = 1 to the end. Each index has an expected relationship to its left neighbor: odd positions should be a peak (a[i] >= a[i-1]) and even positions should be a valley (a[i] <= a[i-1]).

Whenever the current pair violates that rule, we simply swap a[i] and a[i-1]. That single swap fixes the current spot, and it never ruins the pair we already settled before it.

Example: [3,5,2,1,6,4]. At i=2 (valley) 2<5 is fine. At i=3 (peak) 1<2 violates, so swap to get …2,1→1,2... continuing this gives [3,5,1,6,2,4], which alternates 3≤5≥1≤6≥2≤4.

It works because each fix only depends on the immediate neighbor, and fixing position i keeps position i-1 valid, so a single left-to-right sweep is enough.

Time: O(n) Space: O(1)