10-line refactored helper + 1-line for each method (detailed explanation with picture illustration)


  • 0

    Key observation: each value change of a key has increment either +1 or -1, so we could use a list to maintain sorted values in O(1) time.

    1. Define a std::list of pair(value, key hashset with same value) sorted in value and a hashmap mapping from key to list iterator.
    2. Max and min key will be located at last and first nodes, respectively.
    3. When increment/decrement value of a key, locate its position in list by hashmap, remove the key from the hashset and insert/emplace into its left or right neighboring node.
      0_1481660695394_Allone.JPG
    class AllOne {
    private:
        typedef pair<int,unordered_set<string>> ValKeys; 
        list<ValKeys> _list;                                 // list of pair(val, keys with same val)
        unordered_map<string, list<ValKeys>::iterator> _pos; // key -> position
        
        void updateVal(string key, int inc) {        
            bool newkey = _pos.count(key) == 0; // insert a new key                
            int val = inc + (newkey? 0 : _pos[key]->first); if (val < 0) return; // find value to set               
            auto pos = newkey? _list.begin() : _pos[key]; // remove old, find new position to insert
            if (!newkey) {
              if (pos->second.erase(key), pos->second.empty()) _pos.erase(key), pos = _list.erase(pos); else if (inc > 0) ++pos; 
              if (inc < 0 && pos != _list.begin()) --pos;
            }        
            // insert key for existing value
            if (pos != _list.end() && val == pos->first) pos->second.insert(key), _pos[key] = pos;        
            else if (val) { // insert key for new value
              if (pos != _list.end() && val > pos->first) ++pos;
              _pos[key] = _list.emplace(pos, val, unordered_set<string>({key}));
            }
        }
    public:    
        AllOne() { }    
        void inc(string key) { updateVal(key, 1); }    
        void dec(string key) { updateVal(key, -1); }    
        string getMaxKey() { return _list.empty()? "" : *_list.rbegin()->second.begin(); }    
        string getMinKey() { return _list.empty()? "" : *_list.begin()->second.begin(); }
    };
    

Log in to reply
 

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