First Unique Number in C++

Suppose we have a queue of integers, we need to retrieve the first unique integer in that queue. We have to implement the class called FirstUnique: It will be initialized by the numbers in the queue. Define one function showFirstUnique(), this will return the value of the first unique integer of the queue and returns -1 if there is no such integer. Another method is add(value) this will insert value to the queue.

So, if the input is like

• Initialize with [2,3,4] then call the functions as follows −

• showFirstUnique()

• add(5)

• showFirstUnique()

• add(2)

• showFirstUnique()

• add(3)

• showFirstUnique(),

then the output will be 2, 2, 3, -1 respectively.

To solve this, we will follow these steps −

• Define one queue q

• Define one map cnt

• The initializer will take the array

  • for each element i in nums

    • (increase cnt[i] by 1)

  • for each element i in nums

    • if cnt[i] is same as 1, then −

      • insert i into q

• Define a function showFirstUnique()

• while (not q is empty and cnt[first element of q] > 1), do −

  • delete element from q

• return (if q is empty, then -1, the otherwise first element of q)

• Define a function add(), this will take value,

• (increase cnt[value] by 1)

• if cnt[value] is same as 1, then −

  • insert value into q

Example 

Let us see the following implementation to get a better understanding −

 Live Demo

#include <bits/stdc++.h> using namespace std; class FirstUnique { public:    queue <int> q;    map <int, int> cnt;    FirstUnique(vector<int>& nums) {       for (int i : nums) {          cnt[i]++;       }       for (int i : nums) {          if (cnt[i] == 1) {             q.push(i);          }       }    }    int showFirstUnique() {       while (!q.empty() && cnt[q.front()] > 1) q.pop();          return q.empty() ? -1 : q.front();    }    void add(int value) {       cnt[value]++;       if (cnt[value] == 1)          q.push(value);    } }; main(){    vector<int> v = {2,3,5};    FirstUnique ob(v);    cout << (ob.showFirstUnique()) << endl;    ob.add(5);    cout << (ob.showFirstUnique()) << endl;    ob.add(2);    cout << (ob.showFirstUnique()) << endl;    ob.add(3);    cout << (ob.showFirstUnique()) << endl; }

Input

{2,3,5} ob.showFirstUnique(); ob.add(5); ob.showFirstUnique(); ob.add(2); ob.showFirstUnique(); ob.add(3); ob.showFirstUnique();

Output

2 2 3 -1