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", "get", "put", "get", "get"]
[[1], [2, 1], [2], [3, 2], [2], [3]]
Output
[null, null, 1, null, -1, 2]

Explanation
LRUCache lRUCache = new LRUCache(1);
lRUCache.put(2, 1); // cache is {2=1}
lRUCache.get(2);    // return 1
lRUCache.put(3, 2); // LRU key was 2, evicts key 2, cache is {3=2}
lRUCache.get(2);    // returns -1 (not found)
lRUCache.get(3);    // return 2

Steps

1. Data Structure: Use a combination of a Map (for O(1) key lookup) and a Doubly Linked List (for O(1) insertion and deletion at both ends). The Map will store {key: Node} pairs, where Node is a node in the doubly linked list. The doubly linked list maintains the order of usage, with the most recently used node at the head and the least recently used node at the tail.

2. get(key): Check if the key exists in the map. If it does, move the corresponding node to the head of the list (marking it as most recently used) and return its value. If it doesn't, return -1.

3. put(key, value): Check if the key exists. If it does, update its value and move the node to the head. If it doesn't, create a new node and add it to the head. If the cache is full, remove the tail node (LRU) from the list and the map.

Explanation

The key to achieving O(1) time complexity for both get and put operations is using a doubly linked list to manage the order of elements and a hash map for quick lookups. The doubly linked list allows efficient insertion and deletion at both ends, while the hash map enables O(1) access to nodes based on their keys. When a key is accessed or updated, its corresponding node is moved to the head of the list, ensuring that the most recently used elements are always at the front.

Code

class Node {
    key: number;
    value: number;
    prev: Node | null = null;
    next: Node | null = null;
    constructor(key: number, value: number) {
        this.key = key;
        this.value = value;
    }
}

class LRUCache {
    capacity: number;
    map: Map<number, Node>;
    head: Node | null = null;
    tail: Node | null = null;

    constructor(capacity: number) {
        this.capacity = capacity;
        this.map = new Map();
    }

    get(key: number): number {
        if (!this.map.has(key)) return -1;
        const node = this.map.get(key)!;
        this.moveToHead(node);
        return node.value;
    }

    put(key: number, value: number): void {
        if (this.map.has(key)) {
            const node = this.map.get(key)!;
            node.value = value;
            this.moveToHead(node);
        } else {
            const newNode = new Node(key, value);
            this.addToHead(newNode);
            this.map.set(key, newNode);
            if (this.map.size > this.capacity) {
                this.removeTail();
            }
        }
    }

    addToHead(node: Node) {
        node.next = this.head;
        if (this.head) this.head.prev = node;
        this.head = node;
        if (!this.tail) this.tail = node;
    }

    removeNode(node: Node) {
        if (node.prev) node.prev.next = node.next;
        if (node.next) node.next.prev = node.prev;
        if (this.head === node) this.head = node.next;
        if (this.tail === node) this.tail = node.prev;
    }

    removeTail() {
        if (!this.tail) return;
        const tail = this.tail;
        this.removeNode(tail);
        this.map.delete(tail.key);
    }

    moveToHead(node: Node) {
        this.removeNode(node);
        this.addToHead(node);
    }
}

Complexity

• Time Complexity:

  • get: O(1) - Map lookup and list manipulation are constant time.
  • put: O(1) - Map operations and list manipulations are constant time.

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