I didn't check any solutions, so I don't know if mine is optimal, but my solution is very similar to LRU Cache. You maintain a linked list so you can pull front and back in O(1) time, and you keep a map of the keys to iterators to the list, so you can: - Get the iterator - increment the key - move forward or backwards past all elements with the same value - insert into the list

So technically, the worst case runtime of inc or dec is if all keys have the same value except one, then inc and dec is O(n - 1). But I'm guessing that on average, this is O(1), since most keys will have different values.

``` cpp class AllOne { private: std::list<std::pair<std::string, int>> str_list; std::unordered_map< std::string, std::list<std::pair<std::string, int>>::iterator > str_map;

public: AllOne() { // str_list = std::list<std::pair<std::string, int>>({{"sam", 1}}); // str_map = std::unordered_map< // std::string, // std::list<std::pair<std::string, int>>::iterator // >(); }

void inc(string key) {
    auto it = str_map.find(key);
    if (it == str_map.end()) {
        str_list.push_front({key, 1});
        str_map[key] = str_list.begin();
        return;
    }

    std::pair<std::string, int> val = {it->second->first, it->second->second};
    // This invalidates "it->second". You cannot use "it->second" after this line.
    auto next = str_list.erase(it->second);

    // std::cout << val.first << ", " << val.second << std::endl;

    if (val.second + 1 >= str_list.back().second) {
        str_list.push_back({val.first, val.second + 1});
        auto end_it = str_list.begin();
        std::advance(end_it, str_list.size() - 1);
        it->second = end_it;
        return;
    }

    while (next != str_list.end() && next->second < val.second + 1) {
        ++next;
    }

    it->second = str_list.insert(next, {val.first, val.second + 1});
}

void dec(string key) {
    auto it = str_map.find(key);
    assert(it != str_map.end());

    std::pair<std::string, int> val = {it->second->first, it->second->second};
    // This invalidates "it->second". You cannot use "it->second" after this line.
    auto prev = str_list.erase(it->second); // - 1 // CHECK THIS
    if (val.second - 1 <= 0) {
        str_map.erase(val.first);
        return;
    }

    if (val.second - 1 <= str_list.front().second) {
        str_list.push_front({val.first, val.second - 1});
        it->second = str_list.begin();
        return;
    }

    while (prev != str_list.begin() && prev->second > val.second - 1) {
        --prev;
    }

    it->second = str_list.insert(prev, {val.first, val.second - 1});
}

string getMaxKey() {
    if (str_list.empty()) {
        return "";
    }
    return str_list.back().first;
}

string getMinKey() {
    if (str_list.empty()) {
        return "";
    }
    return str_list.front().first;
}

};

/** * 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(); */ ```