Introduction Link to heading
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.
Solution Link to heading
This task is a general engineering task with tradeoff between CPU usage and memorry. Let’s rely on golang capability to have cheap and fast maps to cache unique and non-unique numbers. In this case the only complex thing left is implementation of dual-linked queue with two primary methods: push_back and remove. For 20 years in industry I implemented 100+ times dual queue remove and add methods, so just remember this solution and repeat it any time you need.
type Node struct {
val int
prev *Node
next *Node
}
type FirstUnique struct {
non_unique map[int]bool
unique map[int]*Node
head *Node
tail *Node
}
func Constructor(nums []int) FirstUnique {
cache := make(map[int]int)
for _, num := range nums {
cache[num]++
}
this := FirstUnique { make(map[int]bool), make(map[int]*Node), nil, nil }
for _, num := range nums {
if cache[num] == 1 {
this.unique[num] = this.push_back(num)
} else {
this.non_unique[num] = true
}
}
return this
}
func (this *FirstUnique) ShowFirstUnique() int {
if this.head != nil {
return this.head.val
}
return -1
}
func (this *FirstUnique) Add(value int) {
if this.non_unique[value] {
return
}
if node, ok := this.unique[value]; ok {
delete(this.unique, value)
this.remove(node)
this.non_unique[value] = true
} else {
this.unique[value] = this.push_back(value)
}
}
func (this *FirstUnique) push_back(value int) *Node {
if this.head == nil || this.tail == nil {
node := &Node { val: value }
this.head = node
this.tail = node
return node
} else {
node := &Node {
val: value,
prev: this.tail,
}
this.tail.next = node
this.tail = node
return node
}
}
func (this *FirstUnique) remove(node *Node) {
if this.tail == node {
if this.head == this.tail {
this.head = nil
this.tail = nil
return
}
newTail := this.tail.prev
newTail.next = nil
this.tail = newTail
return
}
if this.head == node {
newHead := this.head.next
newHead.prev = nil
this.head = newHead
return
}
left := node.prev
right := node.next
left.next = right
right.prev = left
}
/**
* Your FirstUnique object will be instantiated and called as such:
* obj := Constructor(nums);
* param_1 := obj.ShowFirstUnique();
* obj.Add(value);
*/