LeetCode 146. 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?


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


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]
        return node.value

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]            
            node.value = value
            self.cache[key] = node            
            new_node = ListNode(key, value)
            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]
    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. Required fields are marked *