Skip to content

146. LRU Cache

Medium

Description

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 <= 10⁴
  • 0 <= value <= 10⁡
  • At most 2 * 10⁡ calls will be made to get and put.

Solutions πŸ”’

Approach1: Hash Table + Doubly Linked List

Time complexity: get(key: int), put(key: int, value: int): \(O(1)\)

Space complexity: \(O(capacity)\)

Algorithm

We can implement an LRU (Least Recently Used) cache using a "hash table" and a "doubly linked list".

  • Hash Table: Used to store cache entries for O(1) access.
  • Doubly Linked List: Used to maintain the order of usage, with head being the most recently used and tail being the least recently used.

Define helper methods to remove a node from the list and to add a node to the head of the list.

  • In the get method, if the key exists, move the corresponding node to the head of the list and return its value.
  • In the put method, if the key exists, remove the old node. Add the new node to the head of the list. If the cache exceeds capacity, remove the node from the tail of the list.

The time complexity is \(O(1)\), and the space complexity is \(O(\textit{capacity})\).

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

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self,node):
        prev_node = node.prev
        next_node = node.next
        prev_node.next = next_node
        next_node.prev = prev_node

    def _add_to_head(self,node):
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:
        if key in self.cache:
            node = self.cache[key]
            self._remove(node)
            self._add_to_head(node)
            return node.value
        return -1

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self._remove(self.cache[key])
        node = Node(key,value)
        self._add_to_head(node)
        self.cache[key] = node
        if len(self.cache)>self.capacity:
            lru = self.tail.prev
            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)

Approach2: Ordered Dictionary

Python Corner

Python provides OrderedDict data structure that helps to implement LRU cache in a much more concise way.

OrderedDict seems to be introduced specifically to implement LRU cache.

OrderedDict vs dict

OrderedDict is not exactly the same as the dict class. dict is fully implemented on the interpreter level. It does preserve the order of inserted keys, but doesn’t expose the move_to_end() method. OrderedDict is partially implemented on the Python level (as dict and a linked list), so it incurs some memory overhead.

Time complexity: get(key: int), put(key: int, value: int): \(O(1)\)

Space complexity: \(O(capacity)\)

Example 
>>> od = collections.OrderedDict()
>>>
>>> od[1]=1
>>> od[2]=2
>>> od[3]=3
>>>
>>> od
OrderedDict([(1, 1), (2, 2), (3, 3)])
>>> od.move_to_end(1)
>>> od
OrderedDict([(2, 2), (3, 3), (1, 1)])
>>>
>>> od.get(1)
1
>>> od.popitem()
(1, 1)
>>> od
OrderedDict([(2, 2), (3, 3)])
>>>
>>> od[1]=1
>>> od
OrderedDict([(2, 2), (3, 3), (1, 1)])
>>>
>>> od.popitem(last=False)
(2, 2)
>>> od
OrderedDict([(3, 3), (1, 1)])

from collections import *

class LRUCache:
    def __init__(self, capacity: 'int'):
        self.cache = OrderedDict()
        self.remain = capacity

    def get(self, key: 'int') -> 'int':
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key) # meaning end is the most recently used
        return self.cache.get(key)

    def put(self, key: 'int', value: 'int') -> 'None':
        if key not in self.cache:
            if self.remain > 0:
                self.remain -= 1
            else:
                self.cache.popitem(last=False) # pop start position
        else:
            self.cache.pop(key)
        self.cache[key] = value # add to end of dict, meaning most recently used

# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
Akhil Singh Chauhan Akhil Singh Chauhan
Creator

Comments