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

Implement the FirstUnique class:

  1. FirstUnique(int[] nums) Initializes the object with the numbers in the queue.
  2. int showFirstUnique() returns the value of the first unique integer of the queue, and returns -1 if there is no such integer.
  3. 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

Solution

A very interesting problem. Use Map to find the duplicate elements. Use Queue to process the input.

C# Program to understand better

public class FirstUnique {

    Queue<int> queue = new Queue<int>();
    Dictionary<int,int> map = new Dictionary<int,int>();
    
    public FirstUnique(int[] nums) {
        for(int i=0;i<nums.Length;i++){
            Add(nums[i]);
        }
    }
    
    public int ShowFirstUnique() {
        while(queue.Count > 0 && map[queue.Peek()] > 1)
            queue.Dequeue();
        
        if(queue.Count == 0)
            return -1;
        
        return queue.Peek();
        
    }
    
    public void Add(int value) {
        if(map.ContainsKey(value)){
            map[value]++;
        }
        else{
            map.Add(value,1);
            queue.Enqueue(value);
        }
    }
}

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

Time Complexity:

  1. For Add() – O(1)
  2. For Insertion – it takes O(n)
  3. For ShowFirstUnique, it takes O(logn)

Space Complexity: O(n)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s