C++ O(1) 0ms AC Solution

  • 0
    class AllOne {
        /** 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 (iters.find(key) == iters.end()) {
                if (ones.empty() || ones.begin()->first != 1) ones.insert(ones.begin(), make_pair(1, KeySet()));
                iters[key] = ones.begin();
            else {
                Ones::iterator it, next;
                it = next = iters[key];
                if (next != ones.end() && next->first == it->first + 1) next->second.insert(key);
                else next = ones.insert(next, make_pair(iters[key]->first + 1, KeySet({ key })));
                iters[key] = next;
                if (it->second.empty()) ones.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 (iters.find(key) != iters.end()) {
                Ones::iterator it, prev;
                prev = it = iters[key];
                if (it != ones.begin()) prev--;
                if (it->first != 1) {
                    if (it == ones.begin() || prev->first != it->first - 1) 
                        prev = ones.insert(it, make_pair(iters[key]->first - 1, KeySet()));
                    iters[key] = prev;
                else iters.erase(key);
                if (it->second.empty()) ones.erase(it);
        /** Returns one of the keys with maximal value. */
        string getMaxKey() {
            return ones.empty() ? "" : *ones.rbegin()->second.begin();
        /** Returns one of the keys with Minimal value. */
        string getMinKey() {
            return ones.empty() ? "" : *ones.begin()->second.begin();
        typedef unordered_set<string> KeySet;
        typedef list<pair<int, KeySet>> Ones;
        Ones ones;
        unordered_map<string, Ones::iterator> iters;

  • 1

    getMaxKey could be like getMinKey, just with ones.rbegin instead of ones.begin.

  • 0

    Thank you so much. I have changed it to rbegin()

  • 1

    About your dec:

    • Where do you check whether the key exists? Is !ones.empty() a mistake?
    • If the key's value is 1, you don't remove it from iters, do you?

  • 0

    I don`t think the Complexity of inc and dec are O(1) because they use unordered_set::erase which is O(n)

  • 0


    Thank you so much for pointing out.
    I add an else statement else iters.erase(key); to remove keys from iters if the key's value is 1.

  • 0

    @Ren.W I see you did some other changes as well. I wrote my own C++ solution yesterday, interesting to see how similar our codes ended up.

    Yours is wrong now, though, you fail for example:

    Your answer:

    Max should be "b", because its value is 2 while "a" only has value 1. Problem is that your first dec turns a=1, b=4 into a=1, b=1 instead of a=1, b=3.

    @1337c0d3r can you add this test case? And fix the C++ judge, because the expected answer is also wrong.

  • 0

    @StefanPochmann Thanks, just added this test case and fixed the C++ solution.

  • 0

    I guess I have fixed the bug :)
    Thank you very much for your comments.

Log in to reply

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