C++ 88ms solution + explanation


  • 1
    L

    There can be improvements in this code, but I did this in less than 30 mins.
    O(1) runtime and O(n) space with linked lists and hash tables.
    Basically what is happening here is, you have a hash table and a list.
    The hash table will have a key, an iterator pointing to a node on the linked list and a value. The linked list will contain nodes of keys.
    Whenever set or get functions are called, the node on the linked list associated with the key will move to the front of the list.
    The hash table will allow us to access at O(1) run time.
    The reason why we have an iterator in the hash table is to allow O(1) run time, else we have to search the list at O(n) run time for the associated key to update.
    The list is to keep track for the least recently used node so we can erase and reuse the keys in the hash table.
    Whenever we find that our hash table has reached its capacity, we will just lookup what is on the back of the list at O(1) search, and use that key to perform our operations on our hash table. The back of the list are the nodes that haven't been touched for the longest time.

    class LRUCache{
    public:
        LRUCache(int capacity) {
            cap = capacity;
        }
        
        int get(int key) {
            std::unordered_map<int,std::pair<std::list<int>::iterator, int>>::iterator got = Hash.find(key);
            if(got!=Hash.end()){
                MoveToFront(key, got);
                return got->second.second;
            }
            return -1;
        }
        
        void set(int key, int value) {
            std::unordered_map<int,std::pair<std::list<int>::iterator, int>>::iterator got = Hash.find(key);
            if(got!=Hash.end()){
                got->second.second = value;
                MoveToFront(key, got);
            }
            else{
                if(Hash.size() == cap){
                    Hash.erase(LRUQueue.back());
                    LRUQueue.pop_back();
                }
                LRUQueue.emplace_front(key);
                Hash[key] = {LRUQueue.begin(), value};
            }
        }
        
        void MoveToFront(int key, const std::unordered_map<int,std::pair<std::list<int>::iterator, int>>::iterator &it){
            LRUQueue.erase(it->second.first);
            LRUQueue.emplace_front(key);
            it->second.first = LRUQueue.begin();
        }
    
    private:
        int cap;
        std::unordered_map<int,std::pair<std::list<int>::iterator, int>> Hash;
        std::list<int> LRUQueue;
    };
    

Log in to reply
 

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