Finding the minimum unique number in an array

Question

The minimum unique number in an array is defined as min{v|v occurs only once in the array} For example, the minimum unique number of {1, 4, 1, 2, 3} is 2. Is there any way better than sorting?

Answer 1

I believe this is an O(N) solution in both time and space:

HashSet seenOnce;     // sufficiently large that access is O(1)
HashSet seenMultiple; // sufficiently large that access is O(1)

for each in input // O(N)
    if item in seenMultiple
        next
    if item in seenOnce
        remove item from seenOnce
        add to item seenMultiple
    else
        add to item seeOnce

smallest = SENTINEL
for each in seenOnce // worst case, O(N)
    if item < smallest
        smallest = item

If you have a limited range of integral values, you can replace the HashSets with BitArrays indexed by the value.