Fully Stable, In-Place Unique Algorithm in O(n)

Question

Is there an algorithm that, given a sorted array, swaps all the first unique elements to the beginning of the array and the duplicates to the end, while remaining stable for both the unique subarray and the duplicate subarray, and that runs in O(n) swaps (and preferably one pass)? It should return the length of the unique portion of the array.

Contrived example input/result (Using python because it's easy to read):

>>> A = [1, 1, 2, 2, 3, 3, 4, 4, 5, 5]   # already sorted
>>> r = Unique(A)
>>> r
5
>>> A
[1, 2, 3, 4, 5, 1, 2, 3, 4, 5]
>>> A[:r] # the sorted portion
[1, 2, 3, 4, 5]
>>> A[r:] # the duplicates portion
[1, 2, 3, 4, 5]

Stability means that even if two or more keys compare equal, the ordering of the keys in the result persists. E.g. if A[i] == A[j] == A[k] and i < j < k in the original array, all of those properties hold in the whole array after running the Unique algorithm. (Even though A[i] might be in the unique subarray and both A[j] & A[k] are in the duplicates subarray.)

My failed attempt is a one-pass that tracks the current unique element while iterating through the array. The next unique element is swapped with the element after the end of the current unique subarray:

def Unique1(A):
    if len(A) <= 1:
        return 0
    i = 0
    for j in range(1, len(A)):
        if A[i] < A[j]:
            i += 1
            if i < j:
                A[i], A[j] = A[j], A[i]
    return i + 1

It swaps the first unique elements of a sorted array to the beginning of the array, runs in one pass (so is O(n)), and is stable for the unique subarray, but this does not satisfy the requirements because it scrambles the duplicates subarray:

>>> A = [1, 1, 2, 2, 3, 3, 4, 4, 5, 5]
>>> r = Unique1(A)
>>> A[r:]          # duplicates part
[3, 2, 4, 1, 5]    # not sorted

While the changes the algorithm makes to the unique subarray is somewhat obvious, I can't "see" what's happening to the duplicates subarray, but I have a feeling that it could be reversed if we knew or stored more information about the duplicates.

Note, just re-sorting the duplicates subarray is a non-starter because 1: it's O(n log n) not O(n) and 2: it breaks the stability.

I can also think of another algorithm that swaps newly found unique items all the way down to the next position. While it would satisfy the other conditions, it would have O(n^2) swaps.

Is such a unique algorithm possible? And if not, why not?

Answer 1

I'm not sure, but I think you need to drop the "preferably one-pass" from your description. You can do it in three passes by using the following algorithm:

• Take a pass over the array, counting the number of unique items as unique_count
• Allocate a new temporary array with size len(A) - unique_count
• Take a second pass over the array, shifting each first instance of an item to the front of the array while copying the second instance to the first free space in the temporary array
• Take a pass over the temporary array, copying each item to its final position in the input array

This is still O(n), albeit with somewhat higher constant factor per item than your original implementation.

Answer 2

If your only reason for the "in-place" requirement is that the elements take up a lot of space, but you can spare O(n) space on the side if the constant factors are low, then this can definitely be done. I warn you, though, that one pass is surely not possible, and, in practice, the number of passes you will need may be very large indeed.

Furthermore, I only know a way to do this probabilistically, which means in the end it is possible that there is some unique value still somewhere in the list which hasn't been extracted. So, you should actually consider this algorithm as being O(n/e) where e is the probability that some unique item was not extracted.

To do this you need to be able to do two things:

1. Identify the first occurrence of each element.
2. Partition the list so that all of those first occurrences are at the beginning.

Both of these need steps need to be done in linear time.

The first one we can accomplish with a Bloom filter. This would be an array of O(k) bits with where k is the number of unique elements in the list. Read the Wikipedia article on bloom filters to get an idea of how the size of the bit array affects the probability of hash collisions, and how to choose the optimal number of hash functions. In order to be able to drive down the probability of failure to any desired level, the hash functions for the filter should be randomized.

In addition to the filter, we also will need another O(n) bitvector.

It should be clear now how we will use these things:

1. Repeat a pre-selected constant number of times:
   1. Pass through the list, checking each element against the Bloom filter before adding it. If the check reveals that this element has never been seen before, mark its position by setting the bit at the same index in the second bitvector.
   2. Clear the Bloom filter, randomize its hash functions.

By now, we have an array of O(n) bits whose ones mark the positions of the first occurrences of the unique values in your list with the desired high probability, so it's on to the second phase: stably partitioning those elements to the beginning of the list. For this we will need to use actual magic. I'm talking about algorithms so complicated it takes more than a single paper to describe all of its parts. I don't even know where to find an implementation! But I guess that's your job.

Yes, we are going to stably partition our bitvectors so that all the ones are at the beginning in linear time. And any time we have to perform a swap to do so, we'll perform a corresponding swap at the same indices in the real array. And in order to do this magical linear-time, stable, in-place partition...

Stable Minimum Space Partitioning in Linear Time - Katajainen and Pasanen, 1992

Don't ask me how that magic works. I don't even have access to the underlying papers.