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.