# Find first unique integer in a stream.

• Design a data structure that support the following methods:
insert(int n); add integer n to a stream of integers.
getFirstUniqueInteger(); return the first unique integer in the stream if found else return -1.

Example:
for input sequence:

insert(2) // 2
insert(2) // -1
insert(3) // 3
insert(4) // 3
insert(3) //4

• My idea is to use a list to store all unique values and use a hash map to record their positions in list (Note: use end() position for duplicated values)

``````class MyContainer
{
private: list<int> unique; // all unique values by insertion order
unordered_map<int, list<int>::iterator> pos; // map value to position in list "unique"

public: // using default constructor
int getFirstUniqueInteger() {
return unique.empty()? -1 : unique.front();
}

void insert(int x) {
// insert new unique value to the tail of list and point to tail position
if (!pos.count(x))
unique.push_back(x), pos[x] = --unique.end();
// mark duplicated values by pointing pos[x] to end
else if (pos[x] != unique.end())
unique.erase(pos[x]), pos[x] = unique.end();
}
};
``````

• @zzg_zzm Good solution!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.