Find the only unique element in an array of a million elements

Question

I was asked this question in a recent interview.

You are given an array that has a million elements. All the elements are duplicates except one. My task is to find the unique element.

var arr = [3, 4, 3, 2, 2, 6, 7, 2, 3........]

My approach was to go through the entire array in a for loop, and then create a map with index as the number in the array and the value as the frequency of the number occurring in the array. Then loop through our map again and return the index that has value of 1.

I said my approach would take O(n) time complexity. The interviewer told me to optimize it in less than O(n) complexity. I said that we cannot, as we have to go through the entire array with a million elements.

Finally, he didn't seem satisfied and moved onto the next question.

I understand going through million elements in the array is expensive, but how could we find a unique element without doing a linear scan of the entire array?

PS: the array is not sorted.

Answer 1

I'm certain that you can't solve this problem without going through the whole array, at least if you don't have any additional information (like the elements being sorted and restricted to certain values), so the problem has a minimum time complexity of O(n). You can, however, reduce the memory complexity to O(1) with a XOR-based solution, if every element is in the array an even number of times, which seems to be the most common variant of the problem, if that's of any interest to you:

int unique(int[] array)
{
    int unpaired = array[0];
    for(int i = 1; i < array.length; i++)
        unpaired = unpaired ^ array[i];
    return unpaired;
}

Basically, every XORed element cancels out with the other one, so your result is the only element that didn't cancel out.

Answer 2

Assuming the array is un-ordered, you can't. Every value is mutually exclusive to the next so nothing can be deduced about a value from any of the other values?

If it's an ordered array of values, then that's another matter and depends entirely on the ordering used.

I agree the easiest way is to have another container and store the frequency of the values.