146. LRU Cache — LeetCode(Python)

I got you!

Problem:

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

• LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
• int get(int key) Return the value of the key if the key exists, otherwise return -1.
• void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.

Example 1:

Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]
Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1);    // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2);    // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1);    // return -1 (not found)
lRUCache.get(3);    // return 3
lRUCache.get(4);    // return 4

Constraints:

• 1 <= capacity <= 3000
• 0 <= key <= 104
• 0 <= value <= 105
• At most 2 * 105 calls will be made to get and put.

Solution:

class Node:
    def __init__(self, key=0, val=0):
        self.key, self.val = key, val
        self.prev = self.next = None
class LRUCache:
def __init__(self, capacity: int):
        self.cap = capacity
        self.cache = {}
        self.left, self.right = Node(), Node()
        self.left.next, self.right.prev = self.right, self.left
        
    
    def remove(self, node):
        l = node.prev
        r = node.next
        l.next = r
        r.prev = l
        
    
    def insert(self, node):
        last = self.right.prev
        last.next = node
        node.next = self.right
        node.prev = last
        self.right.prev = node
def get(self, key: int) -> int:
        if key in self.cache:
            self.remove(self.cache[key]) #remove from wherever it was in the linked list
            self.insert(self.cache[key]) #insert it into the right end(mru)
            return self.cache[key].val
        return -1
def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.remove(self.cache[key]) #remove if already exists
        self.cache[key] = Node(key, value)
        self.insert(self.cache[key]) #insert as mru
        
        if len(self.cache) > self.cap:
            lru = self.left.next
            self.remove(lru)       
            del self.cache[lru.key]
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

Explanation:

We use a doubly linked list and a hash map to solve this problem.

Every key value pair that we are given, we map it to a Node that contains the same key and value.

If the length of the cache is greater than the capacity, we remove the least recently used Node.

We use a left pointer to denote the least recently used Node and a right pointer to denote the most recently used Node.

This is why, whenever we use a put() or get() method, we insert the given node to the end of the list.

The remove() and insert() methods help us remove a given node from the doubly linked list and insert a new node to the right end of the list respectively.

Rest of the code is redundant object-oriented code that should be easy to follow.

Time and Space Complexity —

Since each method in our class performs and O(1) operation, we can say we need a constant amount of time for our algorithm to run.

Also, we require linear amount of space to store each {key : key, value} pair and also the nodes in our doubly linked list.

Thus, if n is the number of key-value pairs we are given to operate on,

Time Complexity: O(1)

Space Complexity: O(n)

Feel free to ask any related questions in the comment section or the links provided down below.

I don’t have friends:

Let’s be friends!

Connect with me on:

LinkedIn

GitHub

Instagram (I know. Very professional)

Jai Shri Ram 🙏