Leetcode 432 Solution

class AllOne {
    struct Bucket
    {
        int val;
        unordered_set<string> keys;
    };

    list<Bucket> l;
    unordered_map<string, list<Bucket>::iterator> m;

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

    void display()
    {
        for (auto it = l.begin(); it != l.end(); it++)
        {
            printf("%d:", it->val);
            for (auto key : it->keys)
                printf("%s ", key.c_str());
            printf("\n");
        }
        printf("\n");
    }

    /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
    void inc(string key) {
        if (m.find(key) == m.end())
        {
            if (l.front().val != 1)
            {
                Bucket bucket;
                bucket.val = 1;
                l.push_front(bucket);
            }

            auto it = l.begin();
            it->keys.insert(key);
            m[key] = it;
        }
        else
        {
            auto it = m[key];
            it->keys.erase(key);

            auto next_it = it;
            next_it++;
            auto target_it = next_it;

            if (next_it == l.end() || next_it->val > it->val + 1)
            {
                Bucket bucket;
                bucket.val = it->val + 1;
                target_it = l.insert(next_it, bucket);
            }

            target_it->keys.insert(key);
            m[key] = target_it;

            if (it->keys.empty())
                l.erase(it);
        }
    }

    /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
    void dec(string key) {
        if (m.find(key) == m.end())
            return;

        auto it = m[key];
        it->keys.erase(key);

        if (it->val == 1)
        {
            m.erase(key);
            if (it->keys.empty())
                l.erase(it);
            return;
        }

        auto prev_it = it;
        prev_it--;
        auto target_it = prev_it;

        if (it == l.begin() || prev_it->val < it->val - 1)
        {
            Bucket bucket;
            bucket.val = it->val - 1;
            target_it = l.insert(it, bucket);
        }

        target_it->keys.insert(key);
        m[key] = target_it;

        if (it->keys.empty())
            l.erase(it);
    }

    /** Returns one of the keys with maximal value. */
    string getMaxKey() {
        if (l.empty())
            return "";

        return *l.back().keys.begin();
    }

    /** Returns one of the keys with Minimal value. */
    string getMinKey() {
        if (l.empty())
            return "";

        return *l.front().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();
 */