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.
O(2n)
is stillO(n)
.