How to wiggle sort an array in linear time complexity?


The wiggle sort is nums[0]nums[2]nums[4]…

For an input: nums = [1, 5, 1, 1, 6, 4], the expected output is [1, 4, 1, 5, 1, 6] and there can be many other possible outputs satisfying the aforementioned criteria.

I realised that the problem has a pattern: nums[1] will be greatest among nums[0:3], nums[3] will be greatest among nums[3:6],…

So, I targetted at getting the next greatest element. This made me implement the heap:

import heapq   class Solution:     def wiggleSort(self, nums: List[int]) -> None:         """         Do not return anything, modify nums in-place instead.         """         nums_heap = []         for num in nums:             heapq.heappush(nums_heap, -1*num)         i = 1         while i < len(nums):             nums[i] = -1 * heapq.heappop(nums_heap)             i += 2         i = 0         while i<len(nums):             nums[i] = -1 * heapq.heappop(nums_heap)             i += 2  

However, the time complexity of my solution is O(n) along with O(n) space complexity. I want to solve this in O(1) space complexity and that would require me to not use heap(extra space).

How to do that?

The complete question is also posted here.