Testing whether or not an array is distinct in O(N) time and O(1) extra space - is it possible?

user_9892404 0
Viewed 175

So I found this purported interview question(1), that looks something like this

Given an array of length n of integers with unknown range, find in O(n) time and O(1) extra space whether or not it contains any duplicate terms.

There are no additional conditions and restrictions given. Assume that you can modify the original array. If it helps, you can restrict the datatype of the integers to ints (the original wording was a bit ambiguous) - although try not to use a variable with 2^(2^32) bits to represent a hash map.

I know there is a solution for a similar problem, where the maximum integer in the array is restricted to n-1. I am aware that problems like

  1. Count frequencies of all elements in array in O(1) extra space and O(n) time
  2. Find the maximum repeating number in O(n) time and O(1) extra space
  3. Algorithm to determine if array contains n…n+m?

exist and either have solutions, or answers saying that it is impossible. However, for 1. and 2. the problems are stronger than this one, and for 3. I'm fairly sure the solution offered there would require the additional n-1 constraint to be adapted for the task here.

So is there any solution to this, or is this problem unsolvable? If so, is there a proof that it is not solvable in O(n) time and O(1) extra space?

(1) I say purported - I can't confirm whether or not it is an actual interview question, so I can't confirm that anyone thought it was solvable in the first place.

space-complexity time-complexity arrays algorithm
2 Answers

We can sort integer arrays in O(N) time! Therefore, sort and run the well-known algorithm for adjacent distinct.

    bool distinct(int array[], size_t n)
    {
        if (n > 0xFFFFFFFF)
            return true; // Pigeonhole
        else if (n > 0x7FFFFFFF)
            radix_sort(array, n); // Yup O(N) sort
        else
            heapsort(array, n); // N is small enough that heapsort's O(N log (N)) is smaller than radix_sort's O(32N) after constant adjust
        for (size_t i = 1; i < n; i++)
            if (array[i] == array[i - 1])
                return true;
        return false;
    }
user_147680

You can do this in expected linear time by using the original array like a hash table...

Iterate through the array, and for each item, let item, index be the item and its index, and let hash(item) be a value in [0,n). Then:

  1. If hash(item) == index, then just leave the item there and move on. Otherwise,
  2. If item == array[hash(item)] then you've found a duplicate and you're all done. Otherwise,
  3. If item < array[hash(item)] or hash(array[hash(item)]) != hash(item), then swap those and repeat with the new item at array[index]. Otherwise,
  4. Leave the item and move on.

Now you can discard all the array elements where hash(item) == index. These are guaranteed to be the smallest items that hash to their target indexes, and they are guaranteed not to be duplicates.

Move all the remaining items to the front of the array and repeat with the new, smaller, subarray.

Each step takes O(N) time, and on average will remove some significant proportion of the remaining elements, leading to O(N) time overall. We can speed things up by taking advantage all the free slots we're creating in the array, but that doesn't improve the overall complexity.

user_54835260
Related