LRU Cache

Medium Design Data Structures Linked Lists Original on LeetCode

Reported atAmazon Microsoft Apple Netflix Goldman Sachs Oracle Walmart Global Tech PhonePe

LRU Cache is a medium design data structures problem solved with the linked lists pattern. The best approach, optimal (hash map + doubly linked list), runs in O(1) per operation time and O(capacity) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (list ordered by recency) up.

Problem

Build a class LRUCache that stores key–value pairs but can hold at most capacity of them. LRUCache(int capacity) creates an empty cache.

get(int key) returns the value stored for key, or -1 if the key is not in the cache. put(int key, int value) stores the value, replacing the old one if the key is already present. When a put adds a new key to a cache that is already full, the cache first throws out the least recently used key: the one whose last get or put happened longest ago.

Both operations must run in O(1) average time.

Examples

Example 1

Input: LRUCache(2), put(7, 70), put(3, 30), get(7), put(9, 90), get(3), get(9), get(7)
Output: 70, -1, 90, 70
Why: Reading key 7 makes it recent, so adding key 9 to the full cache evicts key 3, the one untouched the longest.

Example 2

Input: LRUCache(1), put(4, 1), put(4, 6), get(4), put(5, 2), get(4), get(5)
Output: 6, -1, 2
Why: Writing key 4 again only updates its value; with room for one entry, adding key 5 pushes key 4 out.

Constraints

1 <= capacity <= 3000
0 <= key <= 10^4
0 <= value <= 10^5
At most 2 * 10^5 calls to get and put in total.
Both get and put must run in O(1) average time.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00

Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

Approach	Time	Space
Brute force (list ordered by recency)	`O(capacity) per operation`	`O(capacity)`
Optimal (hash map + doubly linked list)	`O(1) per operation`	`O(capacity)`

1Brute force (list ordered by recency)

TimeO(capacity) per operationFinding and removing an entry walks the list, which can hold up to `capacity` entries.

SpaceO(capacity)The list stores at most `capacity` entries.

Keep the entries in a plain list where the front is the least recently used and the back is the most recent. Every access searches the list for the key, removes it and appends it at the back. When the list is over capacity, drop the front.

get(key): scan the list; if found, remove the entry, append it at the back and return its value; otherwise return -1.
put(key, value): scan the list and remove the entry with that key if it exists.
Append {key, value} at the back.
If the size is now larger than capacity, remove the first entry.

class LRUCache {
    private final int capacity;
    private final List<int[]> items = new ArrayList<>(); // front = least recent

    public LRUCache(int capacity) {
        this.capacity = capacity;
    }

    private int find(int key) {
        for (int i = 0; i < items.size(); i++) {
            if (items.get(i)[0] == key) return i;
        }
        return -1;
    }

    public int get(int key) {
        int i = find(key);
        if (i < 0) return -1;
        int[] e = items.remove(i);
        items.add(e);
        return e[1];
    }

    public void put(int key, int value) {
        int i = find(key);
        if (i >= 0) items.remove(i);
        items.add(new int[] { key, value });
        if (items.size() > capacity) items.remove(0);
    }
}

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.items = []  # front = least recent, each entry [key, value]

    def _find(self, key: int) -> int:
        for i, e in enumerate(self.items):
            if e[0] == key:
                return i
        return -1

    def get(self, key: int) -> int:
        i = self._find(key)
        if i < 0:
            return -1
        e = self.items.pop(i)
        self.items.append(e)
        return e[1]

    def put(self, key: int, value: int) -> None:
        i = self._find(key)
        if i >= 0:
            self.items.pop(i)
        self.items.append([key, value])
        if len(self.items) > self.capacity:
            self.items.pop(0)

class LRUCache {
    int capacity;
    vector<pair<int, int>> items; // front = least recent

    int find(int key) {
        for (int i = 0; i < (int)items.size(); i++) {
            if (items[i].first == key) return i;
        }
        return -1;
    }

public:
    LRUCache(int capacity) : capacity(capacity) {}

    int get(int key) {
        int i = find(key);
        if (i < 0) return -1;
        pair<int, int> e = items[i];
        items.erase(items.begin() + i);
        items.push_back(e);
        return e.second;
    }

    void put(int key, int value) {
        int i = find(key);
        if (i >= 0) items.erase(items.begin() + i);
        items.push_back({key, value});
        if ((int)items.size() > capacity) items.erase(items.begin());
    }
};

class LRUCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.items = []; // front = least recent, each entry [key, value]
    }

    find(key) {
        for (let i = 0; i < this.items.length; i++) {
            if (this.items[i][0] === key) return i;
        }
        return -1;
    }

    get(key) {
        const i = this.find(key);
        if (i < 0) return -1;
        const e = this.items.splice(i, 1)[0];
        this.items.push(e);
        return e[1];
    }

    put(key, value) {
        const i = this.find(key);
        if (i >= 0) this.items.splice(i, 1);
        this.items.push([key, value]);
        if (this.items.length > this.capacity) this.items.shift();
    }
}

2Optimal (hash map + doubly linked list)

TimeO(1) per operationEach operation does one map lookup and a constant number of pointer changes.

SpaceO(capacity)The map and the list hold at most `capacity` entries.

A doubly linked list keeps the entries in recency order: right after a dummy head is the most recent, right before a dummy tail is the least recent. A hash map from key to node lets you jump straight to any entry, and because the list is doubly linked, a node can be unlinked and moved to the front in O(1).

Create dummy nodes head and tail linked to each other, and an empty map key -> node.
get(key): if the key is missing return -1; otherwise unlink its node, insert it right after head, and return its value.
put(key, value): if the key exists, update the node's value and move it right after head.
Otherwise create a node, insert it after head and add it to the map; if the map is now over capacity, unlink the node before tail and remove its key from the map.

class LRUCache {
    private static class Node {
        int key, val;
        Node prev, next;
        Node(int key, int val) { this.key = key; this.val = val; }
    }

    private final int capacity;
    private final Map<Integer, Node> map = new HashMap<>();
    private final Node head = new Node(0, 0), tail = new Node(0, 0);

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    private void unlink(Node n) {
        n.prev.next = n.next;
        n.next.prev = n.prev;
    }

    private void addFront(Node n) {
        n.next = head.next;
        n.prev = head;
        head.next.prev = n;
        head.next = n;
    }

    public int get(int key) {
        Node n = map.get(key);
        if (n == null) return -1;
        unlink(n);
        addFront(n);
        return n.val;
    }

    public void put(int key, int value) {
        Node n = map.get(key);
        if (n != null) {
            n.val = value;
            unlink(n);
            addFront(n);
            return;
        }
        n = new Node(key, value);
        map.put(key, n);
        addFront(n);
        if (map.size() > capacity) {
            Node lru = tail.prev;
            unlink(lru);
            map.remove(lru.key);
        }
    }
}

class Node:
    def __init__(self, key: int = 0, val: int = 0):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None


class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.map = {}  # key -> Node
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    def _unlink(self, n: Node) -> None:
        n.prev.next = n.next
        n.next.prev = n.prev

    def _add_front(self, n: Node) -> None:
        n.next = self.head.next
        n.prev = self.head
        self.head.next.prev = n
        self.head.next = n

    def get(self, key: int) -> int:
        n = self.map.get(key)
        if n is None:
            return -1
        self._unlink(n)
        self._add_front(n)
        return n.val

    def put(self, key: int, value: int) -> None:
        n = self.map.get(key)
        if n is not None:
            n.val = value
            self._unlink(n)
            self._add_front(n)
            return
        n = Node(key, value)
        self.map[key] = n
        self._add_front(n)
        if len(self.map) > self.capacity:
            lru = self.tail.prev
            self._unlink(lru)
            del self.map[lru.key]

class LRUCache {
    struct Node {
        int key, val;
        Node *prev = nullptr, *next = nullptr;
        Node(int k, int v) : key(k), val(v) {}
    };

    int capacity;
    unordered_map<int, Node*> mp;
    Node* head;
    Node* tail;

    void unlink(Node* n) {
        n->prev->next = n->next;
        n->next->prev = n->prev;
    }

    void addFront(Node* n) {
        n->next = head->next;
        n->prev = head;
        head->next->prev = n;
        head->next = n;
    }

public:
    LRUCache(int capacity) : capacity(capacity) {
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head->next = tail;
        tail->prev = head;
    }

    int get(int key) {
        auto it = mp.find(key);
        if (it == mp.end()) return -1;
        Node* n = it->second;
        unlink(n);
        addFront(n);
        return n->val;
    }

    void put(int key, int value) {
        auto it = mp.find(key);
        if (it != mp.end()) {
            Node* n = it->second;
            n->val = value;
            unlink(n);
            addFront(n);
            return;
        }
        Node* n = new Node(key, value);
        mp[key] = n;
        addFront(n);
        if ((int)mp.size() > capacity) {
            Node* lru = tail->prev;
            unlink(lru);
            mp.erase(lru->key);
            delete lru;
        }
    }
};

class LRUCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.map = new Map(); // key -> node
        this.head = { key: 0, val: 0, prev: null, next: null };
        this.tail = { key: 0, val: 0, prev: null, next: null };
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }

    unlink(n) {
        n.prev.next = n.next;
        n.next.prev = n.prev;
    }

    addFront(n) {
        n.next = this.head.next;
        n.prev = this.head;
        this.head.next.prev = n;
        this.head.next = n;
    }

    get(key) {
        const n = this.map.get(key);
        if (n === undefined) return -1;
        this.unlink(n);
        this.addFront(n);
        return n.val;
    }

    put(key, value) {
        let n = this.map.get(key);
        if (n !== undefined) {
            n.val = value;
            this.unlink(n);
            this.addFront(n);
            return;
        }
        n = { key, val: value, prev: null, next: null };
        this.map.set(key, n);
        this.addFront(n);
        if (this.map.size > this.capacity) {
            const lru = this.tail.prev;
            this.unlink(lru);
            this.map.delete(lru.key);
        }
    }
}

Edge cases to test

Capacity 1: every new key evicts the previous one
put on a key that already exists updates the value and makes it most recent, without evicting anything
get on a missing key returns -1 and must not change the recency order
A get right before an insertion saves that key from eviction

Hints

Hint 1

You need two things at once: find a key fast, and know which key was used least recently. Which structure gives each one?

Hint 2

A hash map finds entries in O(1). A doubly linked list can move any node to the front and drop the tail in O(1) if you already hold the node.

Hint 3

Store map: key -> list node. On every access, unlink the node and re-insert it right after a dummy head; evict the node right before a dummy tail.

FAQ

What is the best time complexity for LRU Cache?

Optimal (hash map + doubly linked list) runs in O(1) per operation time and O(capacity) extra space. Each operation does one map lookup and a constant number of pointer changes.

Which pattern does LRU Cache use?

It is a design data structures problem that uses the linked lists pattern. Other problems with the same pattern: Design Linked List, Design Front Middle Back Queue.

Is there a brute force solution for LRU Cache?

Yes. Brute force (list ordered by recency) takes O(capacity) per operation time and O(capacity) space. Keep the entries in a plain list where the front is the least recently used and the back is the most recent.

Which edge cases should I test for LRU Cache?

Capacity 1: every new key evicts the previous one; put on a key that already exists updates the value and makes it most recent, without evicting anything; get on a missing key returns -1 and must not change the recency order; A get right before an insertion saves that key from eviction.