LRU Cache

NeetCode: LRU Cache · LeetCode: 146. LRU Cache · Difficulty: Medium

Design a cache with a fixed capacity. get(key) returns the value or -1. put(key, value) inserts or updates the key; when the cache is full, it first evicts the least recently used key. Both operations must run in O(1). Reading or writing a key makes it the most recently used.

Example

Text

capacity = 2
put(1, 10); put(2, 20)
get(1)      -> 10       (1 is now the most recent)
put(3, 30)               evicts key 2
get(2)      -> -1

Brute force: a list ordered by recency

Keep (key, value) pairs in an ArrayList<int[]>, least recent first. Every access searches the list for the key and moves that entry to the end. Eviction removes the entry at index 0. Both remove(i) calls shift elements, so they are O(n).

Java

import java.util.ArrayList;
import java.util.List;

class LRUCache {
    private final int capacity;
    private final List<int[]> entries = new ArrayList<>(); // {key, value}, least recently used first

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

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

    public int get(int key) {
        int i = indexOf(key);
        if (i < 0) {
            return -1;
        }
        int[] entry = entries.remove(i); // O(n) shift
        entries.add(entry);              // now the most recent
        return entry[1];
    }

    public void put(int key, int value) {
        int i = indexOf(key);
        if (i >= 0) {
            entries.remove(i); // re-inserted below as the most recent
        } else if (entries.size() == capacity) {
            entries.remove(0); // evict the least recently used
        }
        entries.add(new int[]{key, value});
    }
}

public class Main {
    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2);
        cache.put(1, 10);
        cache.put(2, 20);
        System.out.println(cache.get(1));
        cache.put(3, 30);
        System.out.println(cache.get(2));
        System.out.println(cache.get(3));
    }
}

Output

10
-1
30

entries.remove(i) calls remove(int index) because i is an int, and it returns the removed entry.

Time: O(capacity) per operation. Space: O(capacity).

Optimal: HashMap plus a doubly linked list

Two structures work together:

A HashMap<Integer, Node> finds the node for any key in O(1).
A doubly linked list holds the nodes in recency order. Because each node knows both neighbours, unlinking a node from the middle and inserting it at the front are O(1).

The invariant: walking the list from head to tail visits the keys from most recently used to least recently used, and the map has exactly one node for each key in the list.

Text

HEAD <-> [3] <-> [1] <-> TAIL        map: {3 -> node, 1 -> node}
         newest    oldest
get(1):  detach [1], push it right after HEAD
HEAD <-> [1] <-> [3] <-> TAIL
put(4) when full: evict the node just before TAIL (key 3), then push 4 after HEAD

Storage. Nodes are objects with prev and next fields. Linked structures in Java use null and mutable fields, so no wrapper types are needed. head and tail are sentinels: dummy nodes that always exist. Every real node therefore has a real prev and next, so detach and pushFront never need a case for an empty list or for the first or last element. The most recent entry is head.next; the eviction victim is tail.prev.

Helpers:

detach(node) unlinks the node from its neighbours.
pushFront(node) links the node directly after head.
get and an update in put both do detach then pushFront.
When full, put reuses the victim node for the new key, so the list never holds more than capacity real nodes.

The map is only looked up by key and never iterated, so its unspecified iteration order does not matter. The map holds Integer keys, and get(key) auto-boxes the int argument.

Java

import java.util.HashMap;
import java.util.Map;

class LRUCache {
    private static class Node {
        int key;
        int value;
        Node prev;
        Node next;
    }

    private final int capacity;
    private final Map<Integer, Node> nodeOf = new HashMap<>(); // key -> node
    private final Node head = new Node(); // sentinel before the most recent node
    private final Node tail = new Node(); // sentinel after the least recent node

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail; // sentinels start linked to each other: an empty list
        tail.prev = head;
    }

    /** Unlink a node by joining its two neighbours. */
    private void detach(Node n) {
        n.prev.next = n.next;
        n.next.prev = n.prev;
    }

    /** Link a node between head and the current first node. */
    private void pushFront(Node n) {
        n.prev = head;
        n.next = head.next;
        head.next.prev = n;
        head.next = n;
    }

    public int get(int key) {
        Node n = nodeOf.get(key);
        if (n == null) {
            return -1;
        }
        detach(n); // mark as most recently used
        pushFront(n);
        return n.value;
    }

    public void put(int key, int value) {
        Node n = nodeOf.get(key);
        if (n != null) {
            // Existing key: update the value and make it the most recent.
            n.value = value;
            detach(n);
            pushFront(n);
            return;
        }
        if (nodeOf.size() == capacity) {
            // Full: recycle the least recently used node.
            n = tail.prev;
            detach(n);
            nodeOf.remove(n.key);
        } else {
            n = new Node();
        }
        n.key = key;
        n.value = value;
        nodeOf.put(key, n);
        pushFront(n);
    }
}

public class Main {
    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2);
        cache.put(1, 10);
        cache.put(2, 20);
        System.out.println(cache.get(1));
        cache.put(3, 30);
        System.out.println(cache.get(2));
        System.out.println(cache.get(3));
        cache.put(3, 33);
        cache.put(4, 40);
        System.out.println(cache.get(1));
        System.out.println(cache.get(3));
    }
}

Output

Trace of the example: after put(1), put(2) the list is HEAD, 2, 1, TAIL. get(1) moves 1 to the front: HEAD, 1, 2, TAIL. put(3) finds the cache full, evicts the node before TAIL (key 2) and inserts 3 at the front: HEAD, 3, 1, TAIL. get(2) is not in the map, so it returns -1.

Time: O(1) per operation on average (one hash lookup plus a constant number of reference updates). Space: O(capacity).

Edge cases

get on a missing key returns -1 and changes nothing.
put on an existing key updates the value and refreshes recency without evicting anything.
capacity = 1: every new key evicts the previous one.

How to explain it in an interview

A hash map alone gives O(1) lookup but no recency order; a list alone gives order but O(n) lookup. Combine them.
The map stores key to node; the doubly linked list orders nodes from most to least recently used.
Each node has prev and next, so removing a node from the middle needs no search.
Every get and put moves the touched node to the front; eviction removes the node before the tail.
Sentinel HEAD and TAIL nodes remove the empty-list and end-of-list special cases.
Java nodes are objects linked by references, so unlinking a node is a few field assignments.
All operations are O(1); space is O(capacity).