Wiggle Sort

Asked atAmazon
1Give yourself 5 minutes
2Answer out loud, not in your head
3Then compare with the answer below

The problem

Given an integer array nums, reorder it such that nums[0] <= nums[1] >= nums[2] <= nums[3]....

You may assume the input array always has a valid answer.

Input: nums = [3,5,2,1,6,4] Explanation: We need to ensure that elements alternate between ≤ and ≥. Start from index 1 and adjust if needed. 3 ≤ 5 (correct), 5 ≥ 2 (correct), 2 ≤ 1 (incorrect) → swap 2 and 1, now nums = [3,5,1,2,6,4]. Next, 2 ≤ 6 (correct), 6 ≥ 4 (correct). Output: [3,5,1,6,2,4]. Another valid answer: [1,6,2,5,3,4].

Input: nums = [6,6,5,6,3,8] Output: [6,6,5,6,3,8] Explanation: Check alternating conditions: 6 ≤ 6 (correct), 6 ≥ 5 (correct), 5 ≤ 6 (correct), 6 ≥ 3 (correct), 3 ≤ 8 (correct). Since all conditions are already satisfied, no swaps are needed. Final output: [6,6,5,6,3,8].

**Input : **nums = [5,4,3,2,1]

  • 1 <= nums.length <= 5 * 104
  • 0 <= nums[i] <= 104
  • It is guaranteed that there will be an answer for the given input nums.

cpp

class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        // Your code goes here
    }
};

java

class Solution {
    public void wiggleSort(int[] nums) {
        // Your code goes here
    }
}

python

class Solution(object):
    def wiggleSort(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        # Your code goes here

javascript

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var wiggleSort = function(nums) {
    // Your code goes here
};

csharp

public class Solution
{
    public void WiggleSort(int[] nums)
    {
        // Your code goes here
    }
}

go

func wiggleSort(nums []int) {
    //your code goes here
}
Stuck? Show a way to structure it+
  1. 01Scan from index one onward.
  2. 02At odd indices ensure current is at least the previous value.
  3. 03At even indices ensure current is at most the previous value.
  4. 04Swap adjacent values whenever the local relation fails.

Reference answer

Then expect these follow-ups

  • How does Wiggle Sort II differ when strict inequalities are required?

    Tests: partitioning

  • Why does a local swap not break the previous relation?

    Tests: invariant proof

Hiring now

Software engineer roles are open right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.
  • Senior Software Engineer -.NET

    Tyler Technologies · Annapolis, Maryland

  • Software Development Engineer II

    SaaS Labs · Bengaluru, Karnataka, India

  • Advanced Software Engineer - Product Architect (Legal, Safety, and Risk)

    Metropolitan Transportation Authority · New York, NY

Or practice this question first

Next question