Find first unique integer in a stream.

  • 0

    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.

    for input sequence:

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

  • 2

    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(); 

  • 0

    @zzg_zzm Good solution!

Log in to reply

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