Leetcode 432: All O`one Data Structure

https://leetcode.com/problems/all-oone-data-structure/description/

Notes:

This question is not that straightforward.

We need to think about a data-structure to realize the O(1) operation of adding, erasing, and getting date.

Usually, we can couple a list with a hash map, just like Leetcode 146 LRU cache and 460 LFU cache.

If we know the related address, it is convenient (O(1) in time) to remove and add elements for a list. So a hash map is used to correlate the key with the address (iterator) of the element, which can give O(1) time to access the element.

Please see the code below:

class AllOne {
private:
    struct Bucket{
        int val;
        unordered_set<string> keys;
    };
    list<Bucket> buckets;
    unordered_map<string, list<Bucket>::iterator> mp;

public:

    /** Initialize your data structure here. */
    AllOne() {
     
    }

    /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
    void inc(string key) {
        if(!mp.count(key)) {
            mp[key] = buckets.insert(buckets.begin(), {0, {key}});
        }
        auto nxt = mp[key], bucket = nxt++;
        if(nxt == buckets.end() || nxt->val > bucket->val + 1) {//if nxt does not exit, wee need to create one
            nxt = buckets.insert(nxt, {bucket->val + 1, {}});
        }
        nxt->keys.insert(key);
        mp[key] = nxt;
        bucket->keys.erase(key);//remove key from the previous position
        if(bucket->keys.empty()) buckets.erase(bucket);
    }

    /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
    void dec(string key) {
        if(!mp.count(key)) return;
        auto pre = mp[key], bucket = pre--;
        mp.erase(key);
        if(bucket->val > 1) {
            if(bucket == buckets.begin() || pre->val < bucket->val - 1) {//if pre does not exit, we need to create one
                pre = buckets.insert(bucket, {bucket->val - 1, {}});
            }
            pre->keys.insert(key);
            mp[key] = pre;
        }
        bucket->keys.erase(key);//remove key from the previous position
        if(bucket->keys.empty()) buckets.erase(bucket);
    }

    /** Returns one of the keys with maximal value. */
    string getMaxKey() {
        if(buckets.empty()) return "";
        return *(buckets.rbegin()->keys.begin());
    }

    /** Returns one of the keys with Minimal value. */
    string getMinKey() {
        if(buckets.empty()) return "";
        return *(buckets.begin()->keys.begin());
    }
};
/**
 * Your AllOne object will be instantiated and called as such:
 * AllOne* obj = new AllOne();
 * obj->inc(key);
 * obj->dec(key);
 * string param_3 = obj->getMaxKey();
 * string param_4 = obj->getMinKey();
 */