MediumBlind75Hash TableLinked ListDesign

LRU Cache

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement get and put operations in O(1) average time.

Examples

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]

LRUCache with capacity 2. Operations demonstrate LRU eviction.

Constraints

  • •1 <= capacity <= 3000
  • •0 <= key <= 10^4
  • •0 <= value <= 10^5
  • •At most 2 * 10^5 calls will be made to get and put.

Approaches

Use arrays to store keys and values, updating positions on access.

CodeT: O(n) per operation | S: O(capacity)
class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}
        self.order = []
    def get(self, key):
        if key not in self.cache:
            return -1
        self.order.remove(key)
        self.order.append(key)
        return self.cache[key]
    def put(self, key, value):
        if key in self.cache:
            self.order.remove(key)
        elif len(self.cache) >= self.capacity:
            oldest = self.order.pop(0)
            del self.cache[oldest]
        self.cache[key] = value
        self.order.append(key)

Use Python's OrderedDict which maintains insertion order.

CodeT: O(1) per operation | S: O(capacity)
from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.cache = OrderedDict()
        self.capacity = capacity
    def get(self, key):
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]
    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)

Use a hash map for O(1) lookup and a doubly linked list for O(1) insertion/deletion.

Diagram

cache: {1:Node(1,1), 2:Node(2,2)} DLL: head<->Node(1,1)<->Node(2,2)<->tail get(1): move Node(1,1) to end put(3,3): add Node(3,3), remove LRU (Node(2,2))
CodeT: O(1) per operation | S: O(capacity)
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):
        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):
        node.prev.next = node.next
        node.next.prev = node.prev
    def _add_to_end(self, node):
        node.prev = self.tail.prev
        node.next = self.tail
        self.tail.prev.next = node
        self.tail.prev = node
    def get(self, key):
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self._remove(node)
        self._add_to_end(node)
        return node.val
    def put(self, key, value):
        if key in self.cache:
            self._remove(self.cache[key])
        node = Node(key, value)
        self.cache[key] = node
        self._add_to_end(node)
        if len(self.cache) > self.capacity:
            lru = self.head.next
            self._remove(lru)
            del self.cache[lru.key]

Complexity Comparison

Array-Based LRU
T: O(n) per operationS: O(capacity)

Use arrays to store keys and values, updating positions on access.

OrderedDict
T: O(1) per operationS: O(capacity)

Use Python's OrderedDict which maintains insertion order.

Hash Map + Doubly Linked List
T: O(1) per operationS: O(capacity)

Use a hash map for O(1) lookup and a doubly linked list for O(1) insertion/deletion.

Common Mistakes

Not updating the access order on get operations

Using a singly linked list instead of a doubly linked list

Forgetting to remove the key from the hash map when evicting

Try It Yourself

Copy the optimal solution and run it in our compiler.

▶Open in Compiler
← All Problems