Medium

LRU Cache

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]

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); // evicts key 2, cache is {1=1, 3=3} lRUCache.get(2); // returns -1 (not found) lRUCache.put(4, 4); // 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

Hash Map + Doubly Linked List

Approach

Use a Hash Map to get nodes in O(1) time. Use a Doubly Linked List to maintain order of usage. The most recently used node is kept at the head (right next to dummy head), and the least recently used node is kept at the tail (right before dummy tail). When a node is accessed or added, move/add it to the head. When capacity is exceeded, remove the node before the dummy tail from both the list and the hash map.

Complexity Analysis

Time Complexity

O(1) for get and put

Space Complexity

O(capacity)

This design requires an understanding of how to implement and manipulate a doubly linked list.

Solution.java

1class Node {2    int key, val;3    Node prev, next;4    public Node(int key, int val) {5        this.key = key;6        this.val = val;7    }8}9
10class LRUCache {11    private int capacity;12    private Map<Integer, Node> cache;13    private Node head, tail; // Dummy nodes14
15    public LRUCache(int capacity) {16        this.capacity = capacity;17        this.cache = new HashMap<>();18        this.head = new Node(-1, -1);19        this.tail = new Node(-1, -1);20        head.next = tail;21        tail.prev = head;22    }23    24    // Helper to insert right after head25    private void insert(Node node) {26        node.prev = head;27        node.next = head.next;28        head.next.prev = node;29        head.next = node;30    }31    32    // Helper to remove a node33    private void remove(Node node) {34        node.prev.next = node.next;35        node.next.prev = node.prev;36    }37    38    public int get(int key) {39        if (!cache.containsKey(key)) return -1;40        Node node = cache.get(key);41        remove(node);42        insert(node); // Move to most recently used43        return node.val;44    }45    46    public void put(int key, int value) {47        if (cache.containsKey(key)) {48            Node node = cache.get(key);49            remove(node);50        }51        52        Node newNode = new Node(key, value);53        cache.put(key, newNode);54        insert(newNode);55        56        if (cache.size() > capacity) {57            // Remove LRU node from list and map58            Node lru = tail.prev;59            remove(lru);60            cache.remove(lru.key);61        }62    }63}