12

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.

11
  • Is there anything else we know about the array? Is it sorted? Do we know what unique values are in the array? You are currently spending 2n time going through each element of the array, and then each key of the map, and could avoid the second loop by removing keys from the map as you notice duplicates, but O(2n) is still O(n). Jun 3, 2016 at 22:24
  • @AndrewRueckert - it is not sorted. Array just has all numbers that are repeated in some random order, but only one number won't be repeated.
    – Wild Widow
    Jun 3, 2016 at 22:27
  • Are you sure they said O(n) time complexity, rather than, say, O(n) space complexity? Do you know anything about how many duplicates the duplicated elements have? Jun 3, 2016 at 22:29
  • @user2357112 - they said time complexity, not dealing with space complexity here. duplicates may occur any number of times
    – Wild Widow
    Jun 3, 2016 at 22:30
  • 1
    You have to look at exactly all n elements (worst case, there might be cases where you can deduct otherwise). The last one you look at could reveal that your current candidate is a duplicate. Interviewer was maybe not happy with your explanations and testing you.
    – zapl
    Jun 3, 2016 at 22:31

4 Answers 4

17

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.

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.

1

In fact, since the number of elements in the array was fix, you could do much better than what you have proposed.

By "creating a map with index as the number in the array and the value as the frequency of the number occurring in the array", you create a map with 2^32 positions (assuming the array had 32-bit integers), and then you have to pass though that map to find the first position whose value is one. It means that you are using a large auxiliary space and in the worst case you are doing about 10^6+2^32 operations (one million to create the map and 2^32 to find the element).

Instead of doing so, you could sort the array with some n*log(n) algorithm and then search for the element in the sorted array, because in your case, n = 10^6.

For instance, using the merge sort, you would use a much smaller auxiliary space (just an array of 10^6 integers) and would do about (10^6)*log(10^6)+10^6 operations to sort and then find the element, which is approximately 21*10^6 (many many times smaller than 10^6+2^32).

PS: sorting the array decreases the search from a quadratic to a linear cost, because with a sorted array we just have to access the adjacent positions to check if a current position is unique or not.

1

Your approach seems fine. It could be that he was looking for an edge-case where the array is of even size, meaning there is either no unmatched elements or there are two or more. He just went about asking it the wrong way.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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