@ankush: this is where LinkedHashMap comes into play.

One possibility that comes in mind: * Walk the array, create a hashmap (key is the value in array, value is the count of such values). * Walk the array again and check the count in the hash map, once you hit 1, you have the first unique value. This is O(n) both space and time.

@ankush: That does not matter, you do not need to keep the order in the hash map. You go again through the original array, so you definitely find the first unique value. The hashmap is just for bookkeeping.

@kabajiegara: No, that will not work, consider array "2 1" - if you sort, you'll have "1 2" and would thus return 1, which is the wrong answer because the first unique is 2.

dear utk O(2n) = O(n) != O(n^2)...

An easier one would be to sort the array and since they are asking for the first unique element return the first element that does not appear more than once in the newly sorted array.

Are you sure that this is O(n), it is definitely O(n^2), you go over all items twice.