Leetcode 0324. Wiggle Sort II

Problem statement

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

Solution

Find median of all elements, it can be in average in O(n) with QuickSelect or in O(n) in worst case if we use median of medians. (or O(n\log n) if we use sort, which works quite fast).

Use three pointers similar to Problem 0075 about dutch partitioning problem. However here we need to use a bit different indexes, so we can create first so-called virtal indexes: correspondence between original and new index.

Complexity

If we use proper method for median and do dutch partitiong algorithm like in code, then time complexity will be O(n) and space is O(1).

Code

class Solution:
    def wiggleSort(self, nums):
        n = len(nums)
        median = sorted(nums)[n//2]
        def A(i): return (1+2*i) % (n|1)
        
        beg, mid, end = 0, 0, n - 1
        
        while mid <= end:
            if nums[A(mid)] > median:
                nums[A(beg)], nums[A(mid)] = nums[A(mid)], nums[A(beg)]
                beg += 1
                mid += 1
            elif nums[A(mid)] < median:
                nums[A(mid)], nums[A(end)] = nums[A(end)], nums[A(mid)]
                end -= 1
            else:
                mid += 1