Find First Unique Element

Question

I had this question in interview which I couldn't answer. You have to find first unique element(integer) in the array. For example:

3,2,1,4,4,5,6,6,7,3,2,3

Then unique elements are 1, 5, 7 and first unique of 1.

The Solution required:

O(n) Time Complexity.

O(1) Space Complexity.

I tried saying:

Using Hashmaps, Bitvector...but none of them had space complexity O(1).

Can anyone tell me solution with space O(1)?

Answer 1

Here's a non-rigorous proof that it isn't possible: It is well known that duplicate detection cannot be better than O(n * log n) when you use O(1) space. Suppose that the current problem is solvable in O(n) time and O(1) memory. If we get the index 'k' of the first non-repeating number as anything other than 0, we know that k-1 is a repeated and hence with one more sweep through the array we can get its duplicate making duplicate detection a O(n) exercise.

Again it is not rigorous and we can get into a worst case analysis where k is always 0. But it helps you think and convince the interviewer that it isn't likely to be possible.

http://en.wikipedia.org/wiki/Element_distinctness_problem says: Elements that occur more than n/k times in a multiset of size n may be found in time O(n log k). Here k = n since we want elements that appear more than once.