Wiggle Sort

• Problem statement:
  • Example:
• Approach 1
• Approach 2

Problem statement:

Given an unsorted array nums, reorder it in-place such that nums[0] <= nums[1] >= nums[2] <= nums[3].... URL

Example:

Input: nums = [3,5,2,1,6,4]
Output: One possible answer is [3,5,1,6,2,4]

Approach 1

#collapse-hide
from typing import List

class Solution:
    def wiggleSort(self, nums: List[int]) -> int:
        nums.sort()
        
        for i in range(1, len(nums)-1, 2):
            nums[i], nums[i+1] = nums[i+1], nums[i]
        return nums

sol = Solution()

sol.wiggleSort([3,5,2,1,6,4])

[1, 3, 2, 5, 4, 6]

Worst case performance in Time: $O(nlogn)$

Worst case performance in Space: $O(1)$

Approach 2

#collapse-hide

class Solution:
    def wiggleSort(self, nums: List[int]) -> int:
        for i in range(1, len(nums), 2):
            if i>0 and nums[i] < nums[i-1]:
                nums[i], nums[i-1] = nums[i-1], nums[i]
            if i < len(nums) -1 and nums[i] < nums[i+1]:
                nums[i], nums[i+1] = nums[i+1], nums[i]
        
        return nums

sol = Solution()

sol.wiggleSort([3,5,2,1,6,4])

[3, 5, 1, 6, 2, 4]

Worst case performance in Time: $O(n)$

Worst case performance in Space: $O(1)$