Problem statement

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

Solution

Nothing special here, if we have three elements $a_0 \leqslant a_1 \leqslant a_2$, then just change elements and get $a_0 \leqslant a_2 \geqslant a_3$. The similar trick if we have $a_0 \geqslant a_1 \geqslant a_2$. It is a bit similar to bubble sort, but we need only one pass through data.

Complexity

Time complexity is $O(n)$, space complexity is $O(1)$, because we change our data directly.

Code

class Solution:
    def wiggleSort(self, nums):
        n = len(nums)
        nums[:2] = sorted(nums[:2])
        for i in range(1, n - 1):
            nums[i:i+2] = sorted(nums[i:i+2])[::(1-2*(i%2))]