# How to wiggle sort an array in linear time complexity? 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. 