LRU Cache

TARGET DECK: Leetcode FILE TAGS: Medium

---

Intuition

• Make sure that you create two dummy nodes instead of one.
• Pay close attention to detaching the node and then adding it to the most recently used node on every put and get (since that means that key will have been used).
• Reuse those code portions as needed.

Cards

START Basic Front: LRU Cache Back: Helper functions used for doubly Linked List approach: detach(), evict(), insert(), update()

END

Complexity

Runtime

• $O(1)$ Average time complexity due to HashMap

Space

$O(N)$ to store a HashMap as well as a Linked List

Code

More Modular

class DoubleLLNode:
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.next = None
        self.prev = None
 
class LRUCache:
    def __init__(self, capacity: int):
        self.hm = {}
        self.capacity = capacity
        self.lru = DoubleLLNode(-1, -1)
        self.mru = DoubleLLNode(-1, -1)
        self.lru.next = self.mru
        self.mru.prev = self.lru  
 
    def detach(self, node):
        prev = node.prev
        nxt = node.next
 
        node.prev = None
        node.next = None
 
        prev.next = nxt
        nxt.prev = prev
        return node
 
    def evict(self, node):
        self.detach(node)
        del self.hm[node.key]
 
    # Inserts to MRU
    def insert(self, node):
        prev = self.mru.prev
        prev.next = node
        self.mru.prev = node
        node.prev = prev
        node.next = self.mru
    
    # Update MRU
    def update(self, node):
        self.insert(self.detach(node)) # Update MRU
 
    def get(self, key: int) -> int:
        print(key)
        if key in self.hm:
            val = self.hm[key].val
            self.update(self.hm[key])
            return val
        return -1
 
    def put(self, key: int, value: int) -> None:
        if key in self.hm:
            self.hm[key].val = value
            self.update(self.hm[key])
        else:
            if len(self.hm) == self.capacity:
                self.evict(self.lru.next)
            self.hm[key] = DoubleLLNode(key, value)
            self.insert(self.hm[key])
 
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

Original

class Node:
    def __init__(self, key=0, val=0):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None
 
class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cur_size = 0
        self.hm = {}
        self.lru = Node(-1, -1)
        self.mru = Node(-1, -1)
        self.lru.next = self.mru
        self.mru.prev = self.lru
 
    def detatch_node(self, node):
        prev = node.prev
        next = node.next
        next.prev = prev
        prev.next = next
        node.prev = None
        node.next = None
    
    def add_to_mru(self, node):
        prev = self.mru.prev
        prev.next = node
        self.mru.prev = node
        node.prev = prev
        node.next = self.mru
 
    def get(self, key: int) -> int:
        if key not in self.hm:
            return -1
        node = self.hm[key]
        self.detatch_node(node)
        self.add_to_mru(node)
        return node.val
 
    def put(self, key: int, value: int) -> None:
        if key in self.hm:
            node = self.hm[key]
            self.detatch_node(node)
            self.add_to_mru(node)
            self.hm[key].val = value
        else:
            if self.cur_size == self.capacity:
                node = self.lru.next
                self.detatch_node(node)
                del self.hm[node.key]
                self.cur_size -= 1
 
            node = Node(key, value)
            self.hm[key] = node
            self.add_to_mru(node)
            self.cur_size += 1
 
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

Notes

---

References

• LRU Cache