> ## Documentation Index > Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt > Use this file to discover all available pages before exploring further. > ## Agent Instructions > leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform. > Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package. > Examples are backed by tests; copy them verbatim. # LRU Cache Python Solution with Tests > Tested Python solution for LeetCode 146 with 12 pytest cases. Generate a practice environment with lcpy. LeetCode 146, Medium. Topics: Hash Table, Linked List, Design, Doubly-Linked List. [View on LeetCode](https://leetcode.com/problems/lru-cache/description/). Generate this problem as a practice environment: tested reference solution, 12 [parametrized pytest cases](/practice/testing), and a playground notebook: ```bash theme={"theme":{"light":"github-light","dark":"github-dark"}} lcpy gen -n 146 # by problem number lcpy gen -s lru_cache # by problem name ``` ## 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. ### 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] 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^4 * 0 \<= value \<= 10^5 * At most 2 \* 10^5 calls will be made to get and put ## Solution Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/lru_cache/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/lru_cache/test_solution.py): ```python theme={"theme":{"light":"github-light","dark":"github-dark"}} from collections import OrderedDict from leetcode_py.data_structures.doubly_list_node import DoublyListNode class LRUCache: # Space: O(capacity) def __init__(self, capacity: int) -> None: self.capacity = capacity self.cache: OrderedDict[int, int] = OrderedDict() # Time: O(1) # Space: O(1) def get(self, key: int) -> int: if key not in self.cache: return -1 # Move to end (most recent) self.cache.move_to_end(key) return self.cache[key] # Time: O(1) # Space: O(1) def put(self, key: int, value: int) -> None: if key in self.cache: # Update existing and move to end self.cache[key] = value self.cache.move_to_end(key) else: # Add new if len(self.cache) >= self.capacity: # Remove LRU (first item) self.cache.popitem(last=False) self.cache[key] = value class CacheNode(DoublyListNode[int]): def __init__(self, key: int = 0, val: int = 0) -> None: super().__init__(val) self.key = key class LRUCacheWithDoublyList: def __init__(self, capacity: int) -> None: self.capacity = capacity self.cache: dict[int, CacheNode] = {} # Dummy head and tail nodes self.head = CacheNode() self.tail = CacheNode() self.head.next = self.tail self.tail.prev = self.head def _add_node(self, node: CacheNode) -> None: """Add node right after head""" node.prev = self.head node.next = self.head.next if self.head.next: self.head.next.prev = node self.head.next = node def _remove_node(self, node: CacheNode) -> None: """Remove node from list""" if node.prev: node.prev.next = node.next if node.next: node.next.prev = node.prev def _move_to_head(self, node: CacheNode) -> None: """Move node to head (most recent)""" self._remove_node(node) self._add_node(node) def _pop_tail(self) -> CacheNode: """Remove last node before tail""" last_node = self.tail.prev assert isinstance(last_node, CacheNode), "Expected CacheNode" self._remove_node(last_node) return last_node def get(self, key: int) -> int: node = self.cache.get(key) if not node: return -1 # Move to head (most recent) self._move_to_head(node) return node.val def put(self, key: int, value: int) -> None: node = self.cache.get(key) if node: # Update existing node.val = value self._move_to_head(node) else: # Add new new_node = CacheNode(key, value) if len(self.cache) >= self.capacity: # Remove LRU tail = self._pop_tail() del self.cache[tail.key] self.cache[key] = new_node self._add_node(new_node) ``` ## Complexity | Time | Space | | ---- | ----------- | | O(1) | O(capacity) | ## Tags [Grind 75](/catalog/grind-75), [Grind](/catalog/grind), [NeetCode 150](/catalog/neetcode-150), [NeetCode 250](/catalog/neetcode-250), [NeetCode All](/catalog/neetcode), [AlgoMaster 75](/catalog/algo-master-75).