How to Design a First Unique Number Class with O(1)?

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:

1 2	["FirstUnique","showFirstUnique","add","showFirstUnique","add","showFirstUnique","add","showFirstUnique"] [[[2,3,5]],[],[5],[],[2],[],[3],[]]

["FirstUnique","showFirstUnique","add","showFirstUnique","add","showFirstUnique","add","showFirstUnique"]
[[[2,3,5]],[],[5],[],[2],[],[3],[]]

Output:
[null,2,null,2,null,3,null,-1]

Explanation:

1 2 3 4 5 6 7 8

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

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:

1 2	["FirstUnique","showFirstUnique","add","add","add","add","add","showFirstUnique"] [[[7,7,7,7,7,7]],[],[7],[3],[3],[7],[17],[]]

["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:

1 2 3 4 5 6 7 8

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

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:

1 2	["FirstUnique","showFirstUnique","add","showFirstUnique"] [[[809]],[],[809],[]]

["FirstUnique","showFirstUnique","add","showFirstUnique"]
[[[809]],[],[809],[]]

Output:
[null,809,null,-1]

Explanation:

1 2 3 4

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

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.

Hints:
Use doubly Linked list with hashmap of pointers to linked list nodes. add unique number to the linked list. When add is called check if the added number is unique then it have to be added to the linked list and if it is repeated remove it from the linked list if exists. When showFirstUnique is called retrieve the head of the linked list.
Use queue and check that first element of the queue is always unique.
Use set or heap to make running time of each function O(logn).

1
2
3
4

// Your FirstUnique object will be instantiated and called as such:
FirstUnique* obj = new FirstUnique(nums);
int param_1 = obj->showFirstUnique();
obj->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);

First Unique Number using Double-Linked Queue and Hash Map

The key to design a O(1) data structure which allows to retrieve the first unqiue number and add a number to the queue is to use a double linked list and a hash map.

The elements in the double linked list are always unique. And the hash map allows us to retrieve a linked node in constant time. And, also we need to maintain a head and tail dummy node, which allows us to add a new node to the end of the double linked list, and retrieve the head of the double linked list.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

class FirstUnique {
public:
    struct ListNode {
        int val;
        ListNode* prev;
        ListNode* next;
        ListNode(int val) {
            this->val = val;
            prev = nullptr;
            next = nullptr;
        }
    };
    
    FirstUnique(vector<int>& nums) {
        dummy = new ListNode(-1);
        tail = new ListNode(-1);  
        for (const auto &n: nums) {
            add(n);
        }
    }
    
    int showFirstUnique() {
        if (dummy->next == nullptr) return -1;
        return dummy->next->val;
    }
    
    void add(int value) {
        // element is already added before
        if (data.find(value) != data.end()) {
            ListNode* cur = data[value];
            if (cur == nullptr) return;
            if (cur->prev) {
                cur->prev->next = cur->next;
            }
            if (cur->next) {
                cur->next->prev = cur->prev;
            }
            if (cur == dummy->next) {
                dummy->next = cur->next;
            }
            if (tail->next == cur) {
                tail->next = cur->prev;
            }
            data[value] = nullptr;
        } else { // new unique number
            ListNode *cur = new ListNode(value);
            if (dummy->next == nullptr) {
                dummy->next = cur;
            }
            if (tail->next) {
                tail->next->next = cur;
                cur->prev = tail->next;
            }   
            tail->next = cur;
            data[value] = cur;
        }
    }
private:
    unordered_map<int, ListNode*> data;
    ListNode *dummy;
    ListNode *tail;
};

class FirstUnique {
public:
    struct ListNode {
        int val;
        ListNode* prev;
        ListNode* next;
        ListNode(int val) {
            this->val = val;
            prev = nullptr;
            next = nullptr;
        }
    };
    
    FirstUnique(vector<int>& nums) {
        dummy = new ListNode(-1);
        tail = new ListNode(-1);  
        for (const auto &n: nums) {
            add(n);
        }
    }
    
    int showFirstUnique() {
        if (dummy->next == nullptr) return -1;
        return dummy->next->val;
    }
    
    void add(int value) {
        // element is already added before
        if (data.find(value) != data.end()) {
            ListNode* cur = data[value];
            if (cur == nullptr) return;
            if (cur->prev) {
                cur->prev->next = cur->next;
            }
            if (cur->next) {
                cur->next->prev = cur->prev;
            }
            if (cur == dummy->next) {
                dummy->next = cur->next;
            }
            if (tail->next == cur) {
                tail->next = cur->prev;
            }
            data[value] = nullptr;
        } else { // new unique number
            ListNode *cur = new ListNode(value);
            if (dummy->next == nullptr) {
                dummy->next = cur;
            }
            if (tail->next) {
                tail->next->next = cur;
                cur->prev = tail->next;
            }   
            tail->next = cur;
            data[value] = cur;
        }
    }
private:
    unordered_map<int, ListNode*> data;
    ListNode *dummy;
    ListNode *tail;
};

Both operations are done in O(1) constant time, and O(N) space is required as we are using double linked list and a hash map to store the numbers in the queue.

–EOF (The Ultimate Computing & Technology Blog) —