The wiggle sort is numsnumsnums…
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 will be greatest among nums[0:3], nums 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.