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

Explanation

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

Steps

  1. Data Structure: Use a combination of a doubly linked list and a HashMap. The doubly linked list maintains the order of elements (most recently used at the head, least recently used at the tail). The HashMap provides O(1) lookup for keys.

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

  3. put(key, value): Check if the key exists in the HashMap.

    • If it does, update its value and move the node to the head of the linked list.
    • If it doesn't:
      • If the cache is full (size equals capacity), remove the tail node (LRU element) from both the list and the HashMap.
      • Add the new (key, value) pair to the head of the linked list and the HashMap.

Explanation

The core idea is to leverage the strengths of both a doubly linked list and a hash map. The doubly linked list efficiently manages the order of access, allowing for O(1) insertion and deletion at both ends. The hash map provides O(1) lookup for keys, enabling quick retrieval of values. By combining them, we achieve the O(1) complexity requirement for both get and put operations.

Code

#include <iostream>
#include <unordered_map>

using namespace std;

struct Node {
    int key;
    int value;
    Node *prev;
    Node *next;
    Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};

class LRUCache {
private:
    int capacity;
    unordered_map<int, Node*> cache;
    Node *head;
    Node *tail;

    void removeNode(Node* node) {
        if (node->prev) node->prev->next = node->next;
        if (node->next) node->next->prev = node->prev;
        if (node == tail) tail = node->prev;
        if (node == head) head = node->next;
    }

    void addToHead(Node* node) {
        node->next = head;
        if (head) head->prev = node;
        head = node;
        if (!tail) tail = node;
    }

public:
    LRUCache(int capacity) : capacity(capacity), head(nullptr), tail(nullptr) {}

    int get(int key) {
        if (cache.count(key)) {
            Node* node = cache[key];
            removeNode(node);
            addToHead(node);
            return node->value;
        }
        return -1;
    }

    void put(int key, int value) {
        if (cache.count(key)) {
            Node* node = cache[key];
            node->value = value;
            removeNode(node);
            addToHead(node);
        } else {
            Node* newNode = new Node(key, value);
            cache[key] = newNode;
            addToHead(newNode);
            if (cache.size() > capacity) {
                cache.erase(tail->key);
                removeNode(tail);
            }
        }
    }
};

int main() {
    LRUCache cache(2);
    cache.put(1, 1);
    cache.put(2, 2);
    cout << cache.get(1) << endl; // 1
    cache.put(3, 3);
    cout << cache.get(2) << endl; // -1
    cache.put(4, 4);
    cout << cache.get(1) << endl; // -1
    cout << cache.get(3) << endl; // 3
    cout << cache.get(4) << endl; // 4
    return 0;
}

Complexity

  • Time Complexity:

    • get(key): O(1) - HashMap lookup and list manipulation are constant time.
    • put(key, value): O(1) - HashMap operations and list manipulations are constant time. Even eviction of the LRU element is O(1).

  • Space Complexity: O(capacity) - The space used is proportional to the cache capacity. The HashMap and the doubly linked list both store at most capacity elements.