Back to solutions

Wiggle Sort

MediumArrays

Reorder so nums[0] <= nums[1] >= nums[2] <= nums[3]...

Open problem
Constraints
  • 1 <= n <= 10^4
  • 0 <= nums[i] <= 10^4

Greedy local fix

Time O(n)Space O(1)

Walk the array fixing one adjacent pair at a time. At even indices we want nums[i] <= nums[i+1]; at odd indices we want nums[i] >= nums[i+1]. Whenever the required relation is violated, swap the pair. A single swap fixes the local order without breaking the already-processed prefix.

Key terms
wiggle order:
An arrangement that alternately rises and falls between neighbours.
local fix:
Correcting just the current adjacent pair, which is enough to build a global wiggle.
void wiggleSort(vector<int>& nums) {
    for (int i = 0; i + 1 < (int)nums.size(); i++)
        if ((i % 2 == 0) == (nums[i] > nums[i + 1])) swap(nums[i], nums[i + 1]);
}
Step by step
  1. Iterate i from 0 to n-2.
  2. On even i, if nums[i] > nums[i+1], swap them (we want a rise).
  3. On odd i, if nums[i] < nums[i+1], swap them (we want a fall).
  4. Each fix keeps earlier pairs valid, so one pass produces a wiggle order.