Can you help me in finding an algorithm that finds the first unique number in an array with lowest position?

Question

I have the following problem to solve:

Given a non-empty array A consisting of N integers, the task is to find the first unique number in the array. A unique number is defined as a number that occurs exactly once in the array. The desired output is the unique number with the lowest position in the array.

For example, consider the following array A:

   A[0] = 4
   A[1] = 10
   A[2] = 5
   A[3] = 4
   A[4] = 2
   A[5] = 10

In this array, the unique numbers are 5 and 2. The first unique number with the lowest position is 5 because A[2] = 5.

The problem requires an algorithm and the time complexity for finding the first unique number in the given array. The algorithm should be able to handle a generic case where the given array A can have any size N and any set of integers.

Answer 1

Simples. Use a hash table. Fill it with a[n-1], a[n-2] ... a[0] in that order. When you add a number to a hash table you will know if it was there already or not. What you want is the last number you added that wasn't in the hash table before you added it.

(It is obvious that you need to examine all array elements, because one that you don't examine could contain the same value as the array element that you thought was the first unique one, and you would get the wrong answer).

A hash table of reasonable size will work in constant times average.

Answer 2

Here's one idea.

1. Pair up each element with its index.

    [(4, 0), (10, 1), (5, 2), (4, 3), (2, 4), (10, 5)]
   

2. Sort.

    [(2, 4), (4, 0), (4, 3), (5, 2), (10, 1), (10, 5)]
   

3. It is now easy to recognize unique elements, because if any duplicates exist they are right next to each other. Keep only the unique elements.

    [(2, 4), (5, 2)]
   

4. Sort again but on the other half of the pair.

    [(5, 2), (2, 4)]
   

5. Take the first result.