LRU Cache medium

Problem Statement

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

Example 2

Input
["LRUCache", "put", "put", "get", "put", "get", "get"]
[[1], [2, 1], [1, 1], [2], [3, 3], [2], [3]]
Output
[null, null, null, 1, null, -1, 3]

Steps and Explanation

The optimal solution uses a combination of a doubly linked list and a hash map.

1. Doubly Linked List: The doubly linked list maintains the order of elements based on recency. The most recently used item is at the head, and the least recently used is at the tail. This allows for O(1) removal from both ends.

2. Hash Map: The hash map (dictionary in Python) stores key-value pairs, with the key mapping to the node in the doubly linked list. This allows for O(1) lookup of keys.

Operations:

• get(key): Look up the key in the hash map. If found, move the corresponding node to the head of the linked list (marking it as most recently used) and return the value. If not found, return -1.

• put(key, value):

  • If the key exists, update the value and move the node to the head.
  • If the key doesn't exist:
    • If the cache is full, remove the tail node (LRU) from both the linked list and the hash map.
    • Add the new node to the head of the linked list and update the hash map.

Code

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


class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}  # key -> Node
        self.left = Node(0, 0)  # left sentinel node
        self.right = Node(0, 0)  # right sentinel node
        self.left.next = self.right
        self.right.prev = self.left

    def remove(self, node):
        prev, nxt = node.prev, node.next
        prev.next, nxt.prev = nxt, prev

    def insert(self, node):
        prev, nxt = self.right.prev, self.right
        prev.next = nxt.prev = node
        node.next, node.prev = nxt, prev

    def get(self, key: int) -> int:
        if key in self.cache:
            self.remove(self.cache[key])
            self.insert(self.cache[key])
            return self.cache[key].val
        return -1

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.remove(self.cache[key])
        self.cache[key] = Node(key, value)
        self.insert(self.cache[key])
        if len(self.cache) > self.capacity:
            lru = self.left.next
            self.remove(lru)
            del self.cache[lru.key]

Complexity

• Time Complexity:

  • get: O(1)
  • put: O(1)

• Space Complexity: O(capacity) The space used is proportional to the capacity of the cache.