LeetCode 146. LRU Cache

Description

https://leetcode.com/problems/lru-cache/

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) – Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) – Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

The cache is initialized with a positive capacity.

Follow up:
Could you do both operations in O(1) time complexity?

Example:

LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

Explanation

We can use a doubly linked list and hashmap together. Everytime we save a new key value pair, we put the key into the map and create a linked list node as its value. Globally, the linked list shows the order of keys. The list node next to the head is the most recently used key, the list node next to the tail is the least recently used key.

Python Solution

class ListNode:

    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.next = None
        self.prev = None
    

class LRUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        
        self.cache = {}
        
        self.head = ListNode(-1, -1)
        self.tail = ListNode(-1, -1)
        
        self.head.next = self.tail
        self.tail.prev = self.head
        
    def get(self, key: int) -> int:
        
        if key not in self.cache:
            return -1
        
        node = self.cache[key]
        self.remove_node(node)
        self.insert_to_head(node)
        
        return node.value
        

    def put(self, key: int, value: int) -> None:
        
        if key in self.cache:
            node = self.cache[key]            
            node.value = value
                        
            self.remove_node(node)            
            
            self.cache[key] = node            
            self.insert_to_head(node)            
        else:
            new_node = ListNode(key, value)
            self.insert_to_head(new_node)
            self.cache[key] = new_node
            
        if len(self.cache) > self.capacity:
            last_node = self.tail.prev
            self.tail.prev = last_node.prev
            last_node.prev.next = self.tail
            
            del self.cache[last_node.key]
            self.remove_node(last_node)        
            
    
    def remove_node(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
        
        
    def insert_to_head(self, node):
        temp = self.head.next
        node.next = temp
        node.prev = self.head
        self.head.next = node
        temp.prev = node
        

# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
  • Time complexity: O(N).
  • Space complexity: O(N).

Leave a Reply

Your email address will not be published.