☕ DSA Java Articles

Topics › Stacks and Queues › Implementation Problems

LRU Cache

Medium TUF ID 961 A2ZSDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Design a cache with a fixed capacity that supports two operations:

Both a get that finds the key and any put count as a “use” of that key. Both operations must run in O(1) average time.

Constraints: 1 ≤ capacity ≤ 3000, keys and values are non-negative integers, at most 2 × 10^5 calls in total.

All implementations in the Java file share one small interface, so the same test script can drive each of them:

interface Cache {
    int get(int key);
    void put(int key, int value);
}

Example

capacity = 2
put(1, 1)          cache order (most recent first): 1
put(2, 2)          2, 1
get(1)  -> 1       1, 2          (1 becomes most recent)
put(3, 3)          3, 1          (full: evict 2, the least recent)
get(2)  -> -1
put(4, 4)          4, 3          (full: evict 1)
get(1)  -> -1
get(3)  -> 3       3, 4
get(4)  -> 4       4, 3

What the data structure must do. Look up a key by value in O(1) (a hash map can do that). Keep the keys in recency order, move any key to the “most recent” end in O(1), and remove the key at the “least recent” end in O(1) (a linked list can do that, if we can reach a node without searching for it). Neither structure is enough alone, and combining them is the whole solution.

Approach 1: Brute force, a list in recency order

Intuition. Keep {key, value} entries in a list ordered from least to most recently used. Every operation scans for the key. A hit is removed and re-appended at the end, which makes it the most recent. When a new key arrives and the list is full, the front entry is the least recent one, so remove it.

Algorithm.

  1. get: scan for the key; if found, move its entry to the end and return the value; else return -1.
  2. put: remove the key’s entry if it exists; if the list is full, remove the first entry; append {key, value}.
static class BruteLRU implements Cache {
    private final int capacity;
    private final List<int[]> entries = new ArrayList<>();   // {key, value}, least recently used first

    BruteLRU(int capacity) { this.capacity = capacity; }

    public int get(int key) {
        for (int i = 0; i < entries.size(); i++) {
            if (entries.get(i)[0] == key) {
                int[] e = entries.remove(i);
                entries.add(e);                              // now the most recently used
                return e[1];
            }
        }
        return -1;
    }

    public void put(int key, int value) {
        for (int i = 0; i < entries.size(); i++) {
            if (entries.get(i)[0] == key) {
                entries.remove(i);
                break;
            }
        }
        if (entries.size() == capacity) entries.remove(0);  // evict the least recently used
        entries.add(new int[]{key, value});
    }
}

Complexity. O(capacity) per operation: the scan, and ArrayList.remove(i) shifts the elements after i. Space O(capacity). With 2 × 10^5 calls and capacity 3000 that is up to 6 × 10^8 steps.

Note that entries.remove(i) is called with an int, which selects remove(int index). On a List<Integer> this overload trap would matter; here the elements are int[], so there is no ambiguity.

Approach 2: Optimal, hash map plus doubly linked list

Intuition. Keep the entries in a doubly linked list in recency order: the node right after head is the most recent, the node right before tail is the least recent. A doubly linked list can unlink any node in O(1) if we already hold a reference to it, because the node knows both of its neighbours. The hash map provides exactly that: it maps each key to its node.

Two details make the code short and safe:

Algorithm.

  1. get(key): look up the node; if missing return -1. Otherwise unlink it, insert it right after head, and return its value.
  2. put(key, value):
    • If the key exists: update the value, move the node to the front, done. No eviction is needed because the size does not change.
    • Otherwise, if the map is full: unlink tail.prev and remove its key from the map.
    • Create a node, put it in the map, insert it at the front.
static class LRUCache implements Cache {
    private static class Node {
        int key, value;
        Node prev, next;
        Node(int key, int value) { this.key = key; this.value = value; }
    }

    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);   // sentinels; head.next is the most recent

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

    public int get(int key) {
        Node node = map.get(key);
        if (node == null) return -1;
        unlink(node);
        insertFront(node);
        return node.value;
    }

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

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

    private void insertFront(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }
}

Dry run of the first five operations of the example (list shown from head to tail):

operation list after map keys returned
put(1, 1) 1 {1}  
put(2, 2) 2, 1 {1, 2}  
get(1) 1, 2 {1, 2} 1
put(3, 3) 3, 1 {1, 3} evicts 2
get(2) 3, 1 {1, 3} -1

Complexity. O(1) average per operation: one hash map access and a constant number of pointer updates. Space O(capacity) for the map and the nodes.

Approach 3: Library shortcut, LinkedHashMap

Intuition. Java’s LinkedHashMap is precisely “hash map plus doubly linked list”. Constructed with accessOrder = true, it moves an entry to the end of its internal list on every get and put, so iteration order is least recent first. It also calls removeEldestEntry after each insertion; overriding it to return size() > capacity makes the map evict its least recently used entry automatically.

static class LinkedHashMapLRU implements Cache {
    private final LinkedHashMap<Integer, Integer> map;

    LinkedHashMapLRU(int capacity) {
        map = new LinkedHashMap<>(16, 0.75f, true) {          // true = order by access, not insertion
            @Override
            protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
                return size() > capacity;
            }
        };
    }

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

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

Complexity. O(1) average per operation, O(capacity) space.

This is worth knowing for production code. In an interview, expect to be asked to build Approach 2 yourself, because that is what the question is testing. Also note that getOrDefault counts as an access in an access-ordered LinkedHashMap, just like get.

Edge cases and pitfalls