🌱 Keegan's Digital Garden

146. LRU Cache

2 min read

📝 Problem Details

💭What Were My Initial Thoughts?

- given that O(1) complexity is required, a hashmap is useful for fast lookups
- to maintain orering of recently used items, a doubly linked list is helpful for fast insertions, deletions and moving elements
- key challenge of this problem is combining the two above structures to conform to the constraints

💡 Explanation of Solution

- use a hashmap ( unordered_map<int, list<pair<int, int>>:: iterator)

- a doubly linked list (list<pair<int, int>>) stores cache elements in order of recent usage

- when an element is accessed, it is moved to the front of the linked list (most recently used)

- when inserting a new element, if the cache is full, the least recently used element (back of the list is removed)

- the map helps quickly locate elements in th elinked list to move them efficiently

⌛ Complexity Analysis

- get(key): O(1)
	- lookup in the hashmap is O(1)
	- move the accessed node to the front using slice() which is O(1)

- put(key, value) : O(1)
	- if the key exists, move the node to the rfont and update its value O(1)
	- if the key does not exist, insert a new node at the front O(1)
	- if the cache exceeds capacity, remove the LRU node from the back O(1)

💻 Implementation of Solution

class LRUCache {
private:
    int capacity;
    list<pair<int,int>> cache; // doubly linked list to store key-value pairs
    unordered_map<int , list<pair<int,int>>::iterator> map; // hashmap for O(1) lookup
 
public:
    LRUCache(int capacity) {
        this->capacity = capacity;
    }
    
    int get(int key) {
        if(map.find(key) == map.end()) return -1;
 
        // move accessed node to the front
            // move element to the beginning of the list
            // in the same list (self splicing)
            // map[key] is the iterator pointing to the element to move
        cache.splice(cache.begin(), cache, map[key]);
        return map[key]->second;
    }
    
    void put(int key, int value) {
        if(map.find(key) != map.end()) {
            //update value and move to front
            cache.splice(cache.begin(), cache, map[key]);
            map[key]->second = value;
        } else {
            // insert new key-value pair
            if(cache.size() == capacity) {
                // remove LRU element from the linked list and hashmap
                map.erase(cache.back().first);
                cache.pop_back();
            }
            cache.push_front({key, value});
            map[key] = cache.begin();
        }
    }
};
 
/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

Graph View