LRU Cache

MediumLinked List

Design a cache with a capacity that supports get and put in O(1), evicting the least recently used key when full.

Constraints

1 <= capacity <= 3000
At most 2 * 10^5 calls

Hash map plus doubly linked list

Time O(1) per operationSpace O(capacity)

A doubly linked list orders keys by recency (front = most recent). A hash map gives O(1) access to nodes. On access, move the node to the front; when full, evict the tail.

#include <bits/stdc++.h>
using namespace std;

class LRUCache {
    int cap;
    list<pair<int,int>> dll; // front = most recent
    unordered_map<int, list<pair<int,int>>::iterator> mp;
public:
    LRUCache(int capacity) : cap(capacity) {}
    int get(int key) {
        auto it = mp.find(key);
        if (it == mp.end()) return -1;
        dll.splice(dll.begin(), dll, it->second);
        return it->second->second;
    }
    void put(int key, int value) {
        auto it = mp.find(key);
        if (it != mp.end()) {
            it->second->second = value;
            dll.splice(dll.begin(), dll, it->second);
            return;
        }
        if ((int)dll.size() == cap) {
            mp.erase(dll.back().first);
            dll.pop_back();
        }
        dll.push_front({key, value});
        mp[key] = dll.begin();
    }
};