O(1) C++ solution (no loops)


  • 0
    N

    O(1) solution in C++ (no loops). Not the best solution out there because it uses a lot of hashing and non-cached list operations. The idea is to use a linked-list of buckets, where you remove a bucket once it becomes empty, so you don't need to keep track of min/max indices. See comments for a cool optimization that brings the time from ~100ms to ~65ms

    class AllOne {
        class Bucket {
    
            unordered_set <string> keys;
            int val;
            
            public:
            
            int getVal() {return val;}
            
            Bucket(int val_in):val(val_in){}
            
            Bucket():val(0){}
            
            unordered_set <string>::iterator find(string key) {
                return keys.find(key);
            }
            
            void deleteString(string key) {
                keys.erase(keys.find(key));
            }
            
            unordered_set <string>::iterator begin(){
                return keys.begin();
            }
            
            unordered_set <string>::iterator end() {
                return keys.end();
            }
            
            void insert(string key) {
                keys.insert(key);
            }
            
            bool empty() {return keys.empty();}
            size_t size(){return keys.size();}
        };
    
        typedef list <Bucket>::iterator BucketPtr;
    
        unordered_map <string, BucketPtr> directory;
        list <Bucket> buckets;
        
        void print() {
            if (buckets.size() == 0) {
                cout << "Empty structure" << endl;
                return;
            }
            for (BucketPtr i = buckets.begin(); i != buckets.end(); ++i) {
                cout << i->getVal() << ": ";
                for (unordered_set <string>::iterator j = i->begin(); j != i->end(); ++j) {
                    cout << *j << " ";
                }
                cout << endl;
            }
            cout << endl;
        }
    
    
    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 (directory.count(key)) {
                BucketPtr current = directory[key];
                BucketPtr next = current;
                ++next;
                int val = current->getVal();
                if (next == buckets.end() || next->getVal() > val + 1) {
                    next = buckets.insert(next, Bucket(val + 1));
                }
                next->insert(key);
                directory[key] = next;
                current->deleteString(key);
                if (current->size() == 0) {
                    buckets.erase(current);
                }
            }
            else {            
                BucketPtr current = buckets.begin();
                if (current == buckets.end() || current->getVal() > 0) {
                    current = buckets.insert(current, Bucket(0));
                }
                directory[key] = current;
                current->insert(key);
            }
        }
        
        /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
        void dec(string key) {
            if (!directory.count(key)) {
                return;
            }
            BucketPtr current = directory[key];
            if (current->getVal() == 0) {
                current->deleteString(key);
                directory.erase(directory.find(key));
                if (current->empty()) {
                    buckets.erase(current);
                }
            }
            else {
                int val = current->getVal();
                current->deleteString(key);
                BucketPtr prev = current;
                --prev;
                if (current == buckets.begin() || prev->getVal() < val - 1) {
                    prev = buckets.insert(current, Bucket(val - 1));
                }
                prev->insert(key);
                if (current->empty()) {
                    buckets.erase(current);
                }
                directory[key] = prev;
            }
        }
        
        /** Returns one of the keys with maximal value. */
        string getMaxKey() {
            if (buckets.empty()) return "";
            return *(buckets.back().begin());
        }
        
        /** Returns one of the keys with Minimal value. */
        string getMinKey() {
            if (buckets.empty()) return "";
            return *(buckets.front().begin());
        }
        
    };
    

  • 0

    Bit disappointing to read "True O(1)" and then only see average O(1)...


  • 0
    N

    @StefanPochmann Is this because of the worst-case for unordered_set/map? I don't think this is possible otherwise.


  • 0

    @nikhill Yes, it's because unordered_set/map operations are only average O(1), not O(1). And when you explicitly proclaim "true" O(1), then I assume you actually mean O(1) and not just average O(1).


  • 0
    N

    @StefanPochmann Ah I understand. What I meant was that there are a lot of solutions that claim O(1) but have a loop (often in decr) that is worst-case O(n).

    Anyway, I found a cool optimization (though it makes the code uglier). If an item being incremented/decremented is the only member of a bucket and the "neighbor" bucket's value is more than 1 greater or lower, you can just increment/decrement the value of the bucket instead of moving the key to a new bucket. I got my time from ~100ms to ~65ms with this.

    class AllOne {
        class Bucket {
            unordered_set <string> keys;
            int val;
            
            public:
            
            int getVal() {return val;}
            
            Bucket(int val_in):val(val_in){}
            
            Bucket():val(0){}
            
    
            void deleteString(string key) {
                keys.erase(key);
            }
            
            void insert(string key) {
                keys.insert(key);
            }
            
            bool empty() {return keys.empty();}
            
            unordered_set<string>::iterator begin() {return keys.begin();}
            
            unordered_set <string>::iterator end() {return keys.end();}
            
            size_t size() {return keys.size();}
            
            void incVal() {val++;}
            
            void decVal(){val--;}
            
        };
        
        typedef list <Bucket>::iterator BucketPtr;
        unordered_map <string, BucketPtr> directory;
        list <Bucket> buckets;
        
        void print() {
            if (buckets.size() == 0) {
                cout << "Empty structure" << endl;
                return;
            }
            for (BucketPtr i = buckets.begin(); i != buckets.end(); ++i) {
                cout << i->getVal() << ": ";
                for (unordered_set <string>::iterator j = i->begin(); j != i->end(); ++j) {
                    cout << *j << " ";
                }
                cout << endl;
            }
            cout << endl;
        }
    
    
    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 (directory.count(key)) {
                BucketPtr current = directory[key];
                BucketPtr next = current;
                ++next;
                int val = current->getVal();
                //if current bucket size is 1 and the next bucket is not val + 1, we don't      
               //increment the current bucket instead of moving the key 
                if (current->size() == 1 &&
                        (next == buckets.end() || next->getVal() > val + 1)) {
                    current->incVal();
                    return;
                }
                current->deleteString(key);
                if (next == buckets.end() || next->getVal() > val + 1) {
                    next = buckets.insert(next, {val + 1});
                }
                next->insert(key);
                directory[key] = next;
                if (current->size() == 0) {
                    buckets.erase(current);
                }
            }
            else {            
                BucketPtr current = buckets.begin();
                if (current == buckets.end() || current->getVal() > 0) {
                    current = buckets.insert(current, {0});
                }
                directory[key] = current;
                current->insert(key);
            }
        }
        
        /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
        void dec(string key) {
            if (!directory.count(key)) {
                return;
            }
            BucketPtr current = directory[key];
            if (current->getVal() == 0) {
                current->deleteString(key);
                directory.erase(directory.find(key));
                if (current->empty()) {
                    buckets.erase(current);
                }
            }
            else {
                int val = current->getVal();
                BucketPtr prev = current;
                --prev;
               
                //if current bucket size is 1 and the previous bucket is not val - 1, we don't      
               //decrement the current bucket instead of moving the key 
                if (current->size() == 1 &&
                        (current == buckets.begin() || prev->getVal() < val - 1)) {
                    current->decVal();
                    return;
                }
                current->deleteString(key);
                if (current == buckets.begin() || prev->getVal() < val - 1) {
                    prev = buckets.insert(current, {val - 1});
                }
                prev->insert(key);
                if (current->empty()) {
                    buckets.erase(current);
                }
                directory[key] = prev;
            }
        }
        
        /** Returns one of the keys with maximal value. */
        string getMaxKey() {
            if (buckets.empty()) return "";
            return *(buckets.back().begin());
        }
        
        /** Returns one of the keys with Minimal value. */
        string getMinKey() {
            if (buckets.empty()) return "";
            return *(buckets.front().begin());
        }
        
    };
    

  • 0

    @nikhill said in O(1) C++ solution (no loops):

    What I meant was that there are a lot of solutions that claim O(1) but have a loop (often in decr) that is worst-case O(n).

    Yeah, it's a real pity when they do that. Still, I'd go with at most saying "O(1)" (with the common understanding that that means average when hash tables are involved, and as the problem statement surely also means it). Though when I posted my own, I didn't even say it at all. That's because I think in a problem called "All O`one Data structure" and where the challenge is specified as "Perform all these in O(1) time complexity", solutions should be O(1) and we only need to explicitly mention complexities when we don't achieve O(1). I sometimes do that when I have a solution that doesn't fulfill the requirements but which I find interesting nonetheless, for example when it's ridiculously short/simple.


Log in to reply
 

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