Wiggle Sort
AmazonThe 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 herejavascript
/**
* @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+
- 01Scan from index one onward.
- 02At odd indices ensure current is at least the previous value.
- 03At even indices ensure current is at most the previous value.
- 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
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question