An all O(1) c++ solution


  • 0
    J

    I used a hash map and a vector with hash set.
    Hash map makes inc&dec spends O(1) time.
    It's easy to save a minKey&maxKey but sometims a max key or min key would disappear (max/min key becomes not max/min, min key dec into 0...)
    So I used an array with keys as reversed index in order to save every value and keys have that value.
    Some one may say that I used a loop to modify minKey/maxKey, but the cost is shared equally when we made the position gap between the 'missed' minKey/maxKey and the new one.

    class AllOne {
    
    private:
    
        unordered_map<string,int> kv;
        vector<unordered_set<string> > index;
        int max_value;
        int min_value;
    
    public:
    
        AllOne() {
            max_value = 0;
        }
    
        void reset_min_value(int value) {
            if (value < min_value) {
                min_value = value;
            }
            if (max_value > 0) {
                while (index[min_value].size() == 0) {
                    min_value++;
                }
            }
        }
        
        /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
        void inc(string key) {
            unordered_map<string,int>::iterator it = kv.find(key);
            int value = (it == kv.end() ? 0 : it->second);
            // allocate enough spaces for index.
            while (index.size() <= value + 1) {
                index.push_back(unordered_set<string>());
            }
            index[value].erase(key);
            value++;
            index[value].insert(key);
            kv[key] = value;
            if (value > max_value) {
                max_value = value;
            }
            reset_min_value(value);
        }
        
        /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
        void dec(string key) {
            unordered_map<string,int>::iterator it = kv.find(key);
            if (it == kv.end()) {
                return;
            }
            int value = it->second;
            kv.erase(key);
            index[value].erase(key);
            value--;
            if (value > 0) {
                kv[key] = value;
                index[value].insert(key);
            }
            if (value < max_value && index[max_value].size() == 0) {
                max_value--;
            }
            reset_min_value(value);
        }
        
        /** Returns one of the keys with maximal value. */
        string getMaxKey() {
            if (max_value == 0) {
                return "";
            }
            return *(index[max_value].begin());
        }
        
        /** Returns one of the keys with Minimal value. */
        string getMinKey() {
            if (min_value == 0) {
                return "";
            }
            unordered_set<string>::iterator it = index[min_value].begin();
            if (it == index[min_value].end()) {
                return "";
            } else {
                return *it;
            }
        }
    
        void print() {
            cout << "kv:" << endl;
            for (unordered_map<string,int>::iterator it = kv.begin(); it != kv.end(); it++) {
                cout << it->first << " -> " << it->second << endl;
            }
            cout << "index(min:" << min_value << ",max:" << max_value << "):" << endl;
            for (int i = min_value; i <= max_value; i++) {
                if (index[i].size() > 0) {
                    cout << i << "->";
                    for (unordered_set<string>::iterator it = index[i].begin(); it != index[i].end(); it++) {
                        cout << *it << ",";
                    }
                    cout << endl;
                }
            }
        }
    
    };
    

  • 2

    Evidence for my theory that solutions advertised as O(1) are more likely to not be O(1) :-)

    Setup up by calling inc("a") n times. Then every inc("b"); dec("b"); will make your reset_min_value search from 0 to n.


  • 0
    J

    Good case!
    Your theory seems to be true.
    In this case, binarytree like data struct for reversed index may be better than list.


  • 0

    @StefanPochmann Thanks, I have added your test case and this solution indeed run slower (600+ms) compared to the optimal one (<100ms).


  • 0

    @1337c0d3r How often do you do inc("a") and inc("b"); dec("b");? I tried adding the following to the constructor and used "Run Code" (on a small input):

        int n = 10000;
        for (int i=0; i<n; i++)
            inc("a");
        for (int i=0; i<n; i++) {
            inc("b");
            dec("b");
        }
    

    It takes about 1030 ms. The top-voted solution only takes about 29 ms for the same.

    When submitting them (without my added experiment), I do get about 700 ms for the above solution and about 74 ms for the top-voted solution. Wondering whether you have a different ratio between the "a" part and the "b" part, or whether the large test case just increased the overall baseline (I mean, the judge itself taking let's say 60 ms due to loading the test cases). Often I can approximate the baseline with a cheating solution, but in this problem that's not so trivial to do.


  • 0

    @StefanPochmann It is 10000 inc("a") followed by 6050 inc("b"); dec("b");


  • 0
    J

    @StefanPochmann

    Hi,

    Hi think if I use sorted linkedlist to make index, it could resolve this problem.

    1. For this problem, item in index moves only one step for each operation, so sorted-linkedlist's insert/update costs O(1) time. (like bubble sort)
    2. We can get max/min value item in sorted linked list.

Log in to reply
 

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