Wiggle Sort II — LeetCode 324 Python Solution

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.

Example

Input

nums = [1,5,1,1,6,4]

Output

[1,6,1,5,1,4]

Explanation

[1,4,1,5,1,6] is also accepted.

Python solution

class Solution:
    def wiggleSort(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        arr = sorted(nums)
        n = len(arr)
        i, j = (n - 1) >> 1, n - 1
        for k in range(n):
            if k % 2 == 0:
                nums[k] = arr[i]
                i -= 1
            else:
                nums[k] = arr[j]
                j -= 1

Complexity

Pattern: Greedy

Take the locally best option every time — when you can prove that never costs you later. LeetCode 324. Wiggle Sort II is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Greedy.

The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.

Related problems