First Unique Number

You have a queue of integers, you need to retrieve the first unique integer in the queue.
Implement the FirstUnique class:

• FirstUnique(int[] nums) Initializes the object with the numbers in the queue.
• int showFirstUnique() returns the value of the first unique integer of the queue, and returns -1 if there is no such integer.
• void add(int value) insert value to the queue.

Example 1:

Input: 
["FirstUnique","showFirstUnique","add","showFirstUnique","add","showFirstUnique","add","showFirstUnique"]
[[[2,3,5]],[],[5],[],[2],[],[3],[]]
Output: 
[null,2,null,2,null,3,null,-1]

Explanation: 
FirstUnique firstUnique = new FirstUnique([2,3,5]);
firstUnique.showFirstUnique(); // return 2
firstUnique.add(5);            // the queue is now [2,3,5,5]
firstUnique.showFirstUnique(); // return 2
firstUnique.add(2);            // the queue is now [2,3,5,5,2]
firstUnique.showFirstUnique(); // return 3
firstUnique.add(3);            // the queue is now [2,3,5,5,2,3]
firstUnique.showFirstUnique(); // return -1

Example 2:

Input: 
["FirstUnique","showFirstUnique","add","add","add","add","add","showFirstUnique"]
[[[7,7,7,7,7,7]],[],[7],[3],[3],[7],[17],[]]
Output: 
[null,-1,null,null,null,null,null,17]

Explanation: 
FirstUnique firstUnique = new FirstUnique([7,7,7,7,7,7]);
firstUnique.showFirstUnique(); // return -1
firstUnique.add(7);            // the queue is now [7,7,7,7,7,7,7]
firstUnique.add(3);            // the queue is now [7,7,7,7,7,7,7,3]
firstUnique.add(3);            // the queue is now [7,7,7,7,7,7,7,3,3]
firstUnique.add(7);            // the queue is now [7,7,7,7,7,7,7,3,3,7]
firstUnique.add(17);           // the queue is now [7,7,7,7,7,7,7,3,3,7,17]
firstUnique.showFirstUnique(); // return 17

Example 3:

Input: 
["FirstUnique","showFirstUnique","add","showFirstUnique"]
[[[809]],[],[809],[]]
Output: 
[null,809,null,-1]

Explanation: 
FirstUnique firstUnique = new FirstUnique([809]);
firstUnique.showFirstUnique(); // return 809
firstUnique.add(809);          // the queue is now [809,809]
firstUnique.showFirstUnique(); // return -1

Constraints:

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^8
• 1 <= value <= 10^8
• At most 50000 calls will be made to showFirstUnique and add.


class FirstUnique {

    LinkedHashMap<Integer, Integer> count = new LinkedHashMap<Integer, Integer>();
    public FirstUnique(int[] nums) {
        for(int num:nums)
            count.put(num, count.getOrDefault(num, 0)+1);
    }
   
    public int showFirstUnique() {
        for(Map.Entry<Integer, Integer>entry:count.entrySet()){
            if(entry.getValue()==1)
                return entry.getKey();
        }
        return -1;
    }
   
    public void add(int value) {
        count.put(value, count.getOrDefault(value, 0)+1);
    }
}

/**
 * Your FirstUnique object will be instantiated and called as such:
 * FirstUnique obj = new FirstUnique(nums);
 * int param_1 = obj.showFirstUnique();
 * obj.add(value);
 */


 Try it on Leetcode

Here, we suggest you to use LinkedHashMap, because it follows order. If you HashMap, it doesn't follow order and result may vary.

In Constructor,
We are going to store given array to LinkedHashMap. While inserting into map, we are also counting each occurrence of a number using getOrDefault(num, 0)  [i.e.,if that key contains any value it returns that value or else it returns 0 by default.., because we are inserting getOrDefault(num, 0) where num is a key, 0 will be default value] 

In showFirstUnique,
Here we are traversing a map using entryset. If any of entry value is 1, then returns that entry key. Else return -1.

In add method,
It is normal add element to map, as seen in constructor. Since, we are inserting only one value, no need of for loop. 

NOTE:[For learning purposes only]
 
Below is another solution using ArrayList, but it will shows TLE(Time Limit Exceeded) so don't make it run and it is just for learning purposes. Here we are using frequency() method of collections which will return number of occurrences of each number in a list.


class FirstUnique {

    ArrayList<Integer>list = new ArrayList<Integer>();
    public FirstUnique(int[] nums) {
        for(int num:nums)
            list.add(num);
    }
   
    public int showFirstUnique() {
        for(Integer num:list){
            if(Collections.frequency(list, num)==1)
                return num;
        }
        return -1;
    }
   
    public void add(int value) {
        list.add(value);
    }
}

/**
 * Your FirstUnique object will be instantiated and called as such:
 * FirstUnique obj = new FirstUnique(nums);
 * int param_1 = obj.showFirstUnique();
 * obj.add(value);
 */


Please let us know your views in comment section.