# 280. Wiggle Sort

## Description

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.

Example 1:

Input: nums = [3,5,2,1,6,4]
Output: [3,5,1,6,2,4]
Explanation: [1,6,2,5,3,4] is also accepted.


Example 2:

Input: nums = [6,6,5,6,3,8]
Output: [6,6,5,6,3,8]


Constraints:

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

Follow up: Could you solve the problem in O(n) time complexity?

## Solutions

When i is odd, nums[i] >= nums[i-1]

When i is an even number, nums[i] <= nums[i-1]

According to its parity, compare it with its corresponding condition, and if it doesn’t match, just swap the position with the previous number.

• 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])) {
swap(nums, i, i - 1);
}
}
}

private void swap(int[] nums, int i, int j) {
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
}

• '''
math prove:

example [3, 5, 2, 1]
when reaching 2, all good
then next, is 1,
so here comes the question, will the number after 2 violating the wiggle rule?

in example, when reaching 2:
* if [3, 5, 2, 10], so 10 is bigger than 2, then no swap needed according to the if () conditions

* if [3, 5, 2, 1], so previous round, guaranteed that 2 is smaller than 5.
And, now a swap needed meaning the number is smaller than 2, i.e. must be smaller than 5, so wiggle rule is still good

'''
class Solution:
def wiggleSort(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
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]

############

class Solution: # sort list first
def wiggleSort(self, nums: List[int]) -> None:
nums.sort()  # Sort the list in ascending order
n = len(nums)

for i in range(1, n - 1, 2):
nums[i], nums[i + 1] = nums[i + 1], nums[i]  # Swap adjacent elements

"""
If the list has an odd length, the last element will be compared with the second-to-last element
and swapped if necessary to form a wiggle sequence.
"""
if n % 2 == 0 or nums[-1] < nums[-2]:
nums[-1], nums[-2] = nums[-2], nums[-1]

############
import random

class Solution:
def wiggleSort(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
if len(nums) <= 1:
return

# Find the median using quickselect
n = len(nums)
mid = self.quickselect(nums, 0, n-1, (n-1)//2)

# Create an empty array with the same length as nums
ans = [None] * n

# Assign the median to every other element
i = 0
j = n-1 if n % 2 == 1 else n-2
for k in range(n):
if nums[k] < mid:
ans[j] = nums[k]
j -= 2
elif nums[k] > mid:
ans[i] = nums[k]
i += 2
else:
ans[j+1] = mid

# Copy the result back to nums
nums[:] = ans

def quickselect(self, nums, left, right, k):
"""
Returns the k-th smallest element in nums[left:right+1].
"""
if left == right:
return nums[left]

# Partition the subarray around a pivot element
pivot_idx = self.partition(nums, left, right)

# Recursively select on the left or right subarray
if k == pivot_idx:
return nums[k]
elif k < pivot_idx:
return self.quickselect(nums, left, pivot_idx-1, k)
else:
return self.quickselect(nums, pivot_idx+1, right, k)

def partition(self, nums, left, right):
"""
Partitions the subarray nums[left:right+1] using the first element as the pivot.
Returns the final index of the pivot element.
"""
pivot = nums[left]
i, j = left+1, right
while i <= j:
if nums[i] <= pivot:
i += 1
elif nums[j] > pivot:
j -= 1
else:
nums[i], nums[j] = nums[j], nums[i]
nums[left], nums[j] = nums[j], nums[left]
return j


• func wiggleSort(nums []int) {
for i := 1; i < len(nums); 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]
}
}
}

• class Solution {
public:
void wiggleSort(vector<int>& nums) {
for (int i = 1; i < 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]);
}
}
}
};