# Python solution with detailed explanation

• Solution

Wiggle Sort https://leetcode.com/problems/wiggle-sort/

Solution 1: Sorting

• Just sort the array and swap adjacent elements
class Solution(object):
def wiggleSort(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
nums.sort()
i = 1
while i+1 < len(nums):
nums[i], nums[i+1] = nums[i+1], nums[i]
i += 2
return

Solution 2: O(N) solution in one pass

• Assume a1,a2,..a[n-1],a[n] is already wiggle sorted.
• Now we have a[n+1] and we want a[n]<=a[n+1]. This means a[n-1] >=a[n]
• Case 1: a[n] <= a[n+1] - All conditions are satisfied
• Case 2: a[n] > a[n+1]
• Swap and this leads to a[n-1] ? a[n+1] < a[n]
• What is ?. a[n-1] >=a[n]. a[n] > a[n+1]. This means a[n-1]>a[n+1]
• Hence we have a[n-1] > a[n+1] < a[n]
class Solution(object):
def wiggleSort(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
i, less = 0, True
while i+1 < len(nums):
if less:
if nums[i+1] < nums[i]:
nums[i],nums[i+1] = nums[i+1], nums[i]
else:
if nums[i+1] > nums[i]:
nums[i],nums[i+1] = nums[i+1], nums[i]
i, less = i+1, not less
return

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.