Problem statement

Design a cache with a fixed capacity that, when full, throws out the least recently used entry. Write the class LRUCache:

• LRUCache(int capacity) creates an empty cache that holds at most capacity keys.
• int get(int key) returns the value stored for key, or -1 if it is not in the cache. A successful get counts as a use of the key.
• void put(int key, int value) stores value for key, replacing any older value; this also counts as a use. If storing a new key would take the cache past its capacity, first remove the key whose last use is the oldest.

Both get and put must run in O(1) average time.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every void method.

Example 1

Input: ["LRUCache","put","put","get","put","get","put","get","get","get"]
[[2],[1,10],[2,20],[1],[3,30],[2],[4,40],[1],[3],[4]]
Output: [null,null,null,10,null,-1,null,-1,30,40]
Explanation: `get(1)` makes 1 the most recent, so putting 3 evicts 2. Putting 4 then evicts 1 (used before 3), leaving 3 and 4.

Example 2

Input: ["LRUCache","put","put","put","get","put","get"]
[[1],[5,1],[5,2],[6,3],[5],[6,0],[6]]
Output: [null,null,null,null,-1,null,0]
Explanation: With room for one key, updating key 5 keeps it, but putting 6 evicts 5. Overwriting an existing key never evicts anything — the value 0 replaces 3.

Constraints

• 1 <= capacity <= 3000
• 0 <= key <= 10^4
• 0 <= value <= 10^5
• At most 2 * 10^5 calls are made to get and put

Hints for LRU Cache

1. Hint 1

   A hash map gives O(1) lookup by key, but it cannot tell you which key was used longest ago.

2. Hint 2

   Keep the keys in a list ordered by last use: a use moves a key to the front, and eviction takes the key at the back.

3. Hint 3

   Moving an element to the front in O(1) needs a doubly linked list whose nodes the hash map points at directly — the map finds the node, the list relinks it.

How to solve LRU Cache

Combine a hash map with a doubly linked list. The list holds the entries in order of last use (most recent at the front); the map takes a key straight to its list node, so every reorder and every eviction is a constant number of pointer changes.

Approach

1. Keep a sentinel node so the list is circular: head.next is the most recently used entry, head.prev the least.
2. get(key): if the map has no node for key, return -1. Otherwise unlink the node, insert it right after the sentinel and return its value.
3. put(key, value): if the key exists, update the value and move its node to the front.
4. Otherwise, if the cache is full, unlink the node at head.prev and delete its key from the map. Then create a node for (key, value), put it at the front and record it in the map.

Why it works

The list is always ordered by last use: each use moves exactly the used node to the front, which keeps every other node's relative order. So the node at the back is the one whose last use is oldest — the entry LRU eviction must remove — and the map is updated in the same step, so it never points at a removed node.

Complexity

• Time — O(1) average per get and put
• Space — O(capacity)

Pitfalls

• Updating an existing key must not evict anything, even when the cache is full.
• Forgetting that get is a use (it must move the key to the front) is the most common bug.
• Each node must remember its key: eviction starts from the list node and has to delete that key from the map.
• Built-in ordered maps (LinkedHashMap with access order, Python's OrderedDict, insertion-ordered hashes in JavaScript, PHP and Ruby) are this same structure; using them is fine once you can explain what they do.

Reference solution

Python

from collections import OrderedDict

class LRUCache:

    def __init__(self, capacity: int):
        self.cap = capacity
        self.items = OrderedDict()  # a hash map over a doubly linked list, oldest first

    def get(self, key: int) -> int:
        if key not in self.items:
            return -1
        self.items.move_to_end(key)
        return self.items[key]

    def put(self, key: int, value: int) -> None:
        if key in self.items:
            self.items.move_to_end(key)
        elif len(self.items) == self.cap:
            self.items.popitem(last=False)  # evict the least recently used
        self.items[key] = value

Java

class LRUCache {
    private final int cap;
    private final LinkedHashMap<Integer, Integer> map;

    public LRUCache(int capacity) {
        cap = capacity;
        // accessOrder = true: iteration runs from least to most recently used
        map = new LinkedHashMap<Integer, Integer>(16, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
                return size() > cap;
            }
        };
    }

    public int get(int key) {
        return map.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        map.put(key, value);
    }
}

C++

class LRUCache {
    int cap;
    list<pair<int, int>> order; // front = most recently used
    unordered_map<int, list<pair<int, int>>::iterator> where;
public:
    LRUCache(int capacity) : cap(capacity) {}

    int get(int key) {
        auto it = where.find(key);
        if (it == where.end()) return -1;
        order.splice(order.begin(), order, it->second);
        return it->second->second;
    }

    void put(int key, int value) {
        auto it = where.find(key);
        if (it != where.end()) {
            it->second->second = value;
            order.splice(order.begin(), order, it->second);
            return;
        }
        if ((int)order.size() == cap) {
            where.erase(order.back().first);
            order.pop_back();
        }
        order.push_front({key, value});
        where[key] = order.begin();
    }
};

JavaScript

// A hash map from key to node, over a circular doubly linked list with a sentinel:
// head.next is the most recently used entry, head.prev the least.
var LRUCache = function(capacity) {
    this.cap = capacity;
    this.size = 0;
    this.nodes = {};
    this.head = { key: -1, value: 0, prev: null, next: null };
    this.head.prev = this.head;
    this.head.next = this.head;
};

LRUCache.prototype.unlink = function(n) {
    n.prev.next = n.next;
    n.next.prev = n.prev;
};

LRUCache.prototype.pushFront = function(n) {
    n.next = this.head.next;
    n.prev = this.head;
    this.head.next.prev = n;
    this.head.next = n;
};

LRUCache.prototype.get = function(key) {
    var n = this.nodes[key];
    if (n === undefined) return -1;
    this.unlink(n);
    this.pushFront(n);
    return n.value;
};

LRUCache.prototype.put = function(key, value) {
    var n = this.nodes[key];
    if (n !== undefined) {
        n.value = value;
        this.unlink(n);
        this.pushFront(n);
        return;
    }
    if (this.size === this.cap) {
        var lru = this.head.prev;
        this.unlink(lru);
        delete this.nodes[lru.key];
        this.size--;
    }
    n = { key: key, value: value, prev: null, next: null };
    this.nodes[key] = n;
    this.pushFront(n);
    this.size++;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More hash table problems

• Implement Router Medium
• Design Task Manager Medium
• Frequency Tracker Medium
• Find Consecutive Integers from a Data Stream Medium
• Design Memory Allocator Medium
• Longest Uploaded Prefix Medium