1
$\begingroup$

The wiggle sort is nums[0] < nums[1] > nums[2] < nums[3] > 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 targeted 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.

$\endgroup$
2
  • $\begingroup$ Since a heap has been built, which costs $O(n\log n)$ time, your solution runs in $O(n\log n)$ time. $\endgroup$ – John L. May 9 '20 at 2:55
  • $\begingroup$ More generally speaking, it is well-known that any comparison-based sorting algorithm cannot have a time complexity better than $\Theta(n \log n)$. $\endgroup$ – Watercrystal Jun 1 '20 at 16:09
2
$\begingroup$

Some characterizations of wiggle-sort

Skip this section if you would like to see the algorithms right away.$\def\A{\mathcal A}$ $\def\S{\mathcal S}$

Given an array $\A=(\A_0,\A_1, \cdots, \A_{n-1})$ of numbers, let us call the $\lceil n/2\rceil$-th smallest entry in $\A$ as well as each entry that is equal to that entry a median of $\A$. (This definition of median differs slightly from its usual definition when $n$ is even. For example, the median of $(3,4)$ is $3$ instead of $3.5$)

Call $A$ wiggle-sorted if $\A_0<\A_1>\A_2<\A_3>\A_4<\cdots$. Call $A$ wiggle-sortable if we can rearrange its entries so that it becomes wiggle-sorted. An array is always wiggle-sortable if all numbers in it are distinct. If all numbers are not distinct, the array may or may not be wiggle-sortable. For example, $[1,2,2]$ is not wiggle-sortable while $[1,1,2]$ is wiggle-sortable.

A permutation of $\{0,1,\cdots, n-1\}$, $\sigma$, is called a wiggling permutation if $\sigma(\A)=(\A_{\sigma(0)},\A_{\sigma(1)}, \cdots, \A_{\sigma(n-1)})$ is wiggle-sorted as long as $\A$ is sorted.

For all $n$, define a permutation $$w_n=\pmatrix { 0 &1 &2 &3 &4&5&\cdots\\m &n-1 &m-1 &n-2 &m-2 &n-3 &\cdots},$$ where $m=\lceil n/2\rceil-1$. For example, $$w_5=\pmatrix { 0 &1 &2 &3 &4 \\2 &4 &1 &3 &0},$$ $$w_8=\pmatrix { 0 &1 &2 &3 &4&5&6&7\\3 &7 &2 &6 &1 &5 &0 &4}.$$ Characterization of wiggle-sortable arrays. The following propositions are equivalent.

  1. $\A$ is wiggle-sortable of size $n$.
  2. (Not too many medians) The number of medians of $A$ is no more than $\lceil n/2\rceil$.
  3. If we have just sorted $A$ (in the usual sense), then $w_n(\A)$ is wiggle-sorted.

Uniqueness of wiggling permutation. For even size $n$, $w_n$ is the unique wiggle permutation. For odd size $n$, $w_n$ and $\overline{w_n}$ are the only two wiggling permutations, where $\overline{w_n}$ is the "reverse" of $w_n$, i.e., $\overline{w_n}(i)=n-1-w_n(i)$ for all $i$.

This uniqueness explains the fact that all solutions to the wiggle-sort problem arrange the given array the same way basically.


Here is the problem again: given an array of numbers, how can we wiggle-sort it?

A simple approach that runs in $O(n\log n)$ time

The easiest approach to implement, as illustrated in the question, is to sort the array, explicitly or implicitly, and rearrange the array.

Input: an array $\A$ of $n$ numbers with indices $0, 1, n-1$.
Output: None if $\A$ is not wiggle-sortable. Otherwise, return $\A$ that has been wiggle-sorted.
Procedure:

  1. Sort $A$ into a temporary array. (Most sorting libraries run in $O(n\log n)$ time on average.)
  2. Copy the largest number, the next largest number, and so on of the temporary array to $A$ at index $1, 3, 5,\cdots$ until the index is out of bound.
  3. Copy the next largest number, the next largest number, and so on of the temporary array to $A$ at index $0, 2, 4,\cdots$ until all numbers are exhausted.
  4. Check if the $\A$ is wiggle-sorted. Return accordingly.
# assume the given array, nums is wiggle-sortable
def wiggle_sort(nums):
    arr = sorted(nums)
    for i in range(1, len(nums), 2): nums[i] = arr.pop()
    for i in range(0, len(nums), 2): nums[i] = arr.pop()

To achieve better performance, we have to avoid sorting the array.

The outline of a faster algorithm

Procedure:

  1. find the median of $\A$ by some $O(n)$ algorithm.
  2. Count the number of all medians. If it is greater than $\lceil n/2\rceil$, return None.
  3. Put all entries larger than the median in positions with odd indices, $1, 3, 5,\cdots$ in that order.
  4. Put all entries smaller than the median in positions with even indices from the largest-even-indice going downwards.
  5. Fill the remaining entries of $A$ with the median. Return $\A$.

The problem is shifted to how to find the median and arrange the numbers

Find the median in linear time and constant space

To implement the algorithm in linear time and constant space we need to find the median in linear time and constant space.

There are various ways to achieve that deterministically, for example, linear-time in-place selection in less than 3n comparisons, 2005 and linear-time in-place selection with 𝜖⋅𝑁 element moves, 2006. Unfortunately, all these algorithms are somewhat complicated.

We can find the median in average linear time and constant space using a simple algorithm, quickselect. Here is the python code.

def k_smallest(nums, k, start, end):
    """
    Returns the k-th smallest number in nums[start:end+1].
    """
    if k <= 0 or end - start < k - 1:
        return None

    k = start + k - 1

    while True:
        if start >= end:
            return nums[start]

        # pivot = nums[random.randint(start, end)]
        pivot = nums[end]
        left, right, m = start, end, start
        while m <= right:
            if nums[m] < pivot:
                nums[left], nums[m] = nums[m], nums[left]
                left += 1
                m += 1
            elif nums[m] > pivot:
                nums[right], nums[m] = nums[m], nums[right]
                right -= 1
            else:
                m += 1
        if left <= k <= right:
            return pivot
        elif k < left:
            end = left - 1
        else:  # k > right
            start = right + 1

m = k_smallest(nums, (n + 1) // 2, 0, len(nums) - 1)  # m is the median

If we relax the space requirement slightly, we can find the median in linear-time and logarithmic-space using the median of medians algorithm.

Arrange the numbers in linear time and constant space

Once the median has been found, the problem is shifted to arrange the number as specified. Any reasonable implementation will run linear time. What is not obvious is how to do it in constant space as well.

We can imagine the entries of $\A$ is actually arranged in the memory consecutively as $A_1$, $A_3$, $A_5$, $\cdots$, $A_{n_1}$, $A_0$, $A_2$, $A_4$, $\cdots$, $A_{n_0}$, where $n_1$ and $n_0$ are the largest odd and even number not exceeding $n$. Here is the explicit access pattern when $n=8$:
$\quad$ Accessing memory at index 0 actually accesses $A_1$.
$\quad$ Accessing memory at index 1 actually accesses $A_3$.
$\quad$ Accessing memory at index 2 actually accesses $A_5$.
$\quad$ Accessing memory at index 3 actually accesses $A_7$.
$\quad$ Accessing memory at index 4 actually accesses $A_0$.
$\quad$ Accessing memory at index 5 actually accesses $A_2$.
$\quad$ Accessing memory at index 6 actually accesses $A_4$.
$\quad$ Accessing memory at index 7 actually accesses $A_6$.
Or, in general, the memory at the index $p$ refers to $\A_{(1+2p)\pmod{n\,|\, 1}}$.

With this mapping between indices, the problem is transformed to the Dutch national flag problem or, what is the same, the tri-color problem on LeetCode. We can apply the tri-color algorithm almost verbatim, which runs in $O(n)$ time and $O(1)$ space (thanks to StefanPochmann for his post).

# Put numbers larger than pivot at smallest odd-indices. 
# Put numbers smaller than pivot at largest even-indices. 
def tri_color_clustering(nums, pivot):
    n = len(nums)

    def map_index(p):
        return (1 + 2 * p) % (n | 1)

    i, j, k = 0, 0, n - 1
    while j <= k:
        if nums[map_index(j)] > pivot:
            nums[map_index(j)], nums[map_index(i)] = nums[map_index(i)], nums[map_index(j)]
            i += 1
            j += 1
        elif nums[map_index(j)] < pivot:
            nums[map_index(j)], nums[map_index(k)] = nums[map_index(k)], nums[map_index(j)]
            k -= 1
        else:
            j += 1
    # print(nums)

A previous version of this answer shows a simple and fast algorithm to wiggle sort an array in $O(n)$ time and $O(1)$ space, assuming all numbers in the given array are distinct.

$\endgroup$
1
  • $\begingroup$ "The following propositions are equivalent" should have been "The following propositions are equivalent for a number array of size $n$". $\endgroup$ – John L. Jun 2 '20 at 23:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.