LRU Cache (LeetCode 146)

Design Strategy

LRU (Least Recently Used) cache discards the least recently accessed items first.

To satisfy performance requirements, both operations must be O(1):

• get(key) → O(1): Quick lookup via Hash Map.
• put(key, value) → O(1): Quick update using Hash Map + Linked List pointer manipulation.

Data Structure: Combine a Hash Map with a Doubly Linked List.

• Hash Map: Maps key to Node, providing O(1) access.
• Doubly Linked List: Maintains access order. The Head represents the most recently used (MRU) item, while the Tail represents the least recently used (LRU) item.

Implementation

class LRUCache {
    // Doubly Linked List Node
    private static class Node {
        int key, val;
        Node prev, next;
        Node(int k, int v) { key = k; val = v; }
    }

    private final int capacity;
    private final Map<Integer, Node> map = new HashMap<>();
    
    // Sentinel nodes to simplify boundary logic
    private final Node head = new Node(0, 0);
    private final Node tail = new Node(0, 0);

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

    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        Node node = map.get(key);
        // Move to head on every access
        moveToHead(node);
        return node.val;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.val = value;
            moveToHead(node);
        } else {
            Node node = new Node(key, value);
            map.put(key, node);
            addToHead(node);
            if (map.size() > capacity) {
                // Evict the LRU node at the tail
                Node lru = removeTail();
                map.remove(lru.key);
            }
        }
    }

    // ---- Private Helper Methods ----
    private void addToHead(Node node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

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

    private void moveToHead(Node node) {
        removeNode(node);
        addToHead(node);
    }

    private Node removeTail() {
        Node lru = tail.prev;
        removeNode(lru);
        return lru;
    }
}

Using Java's Built-in LinkedHashMap

While LinkedHashMap can implement LRU with minimal code, robust system engineering requires a deep understanding of the manual Doubly Linked List implementation.

class LRUCacheLinkedHashMap extends LinkedHashMap<Integer, Integer> {
    private final int capacity;

    LRUCacheLinkedHashMap(int capacity) {
        // accessOrder = true enables LRU behavior
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    public int get(int key) { return super.getOrDefault(key, -1); }
    public void put(int key, int value) { super.put(key, value); }

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity;
    }
}

LFU Cache (LeetCode 460)

LFU (Least Frequently Used) discards items with the lowest access frequency. If frequencies are tied, it discards the least recently used item among them.

Required tracking:

• keyToVal: key → value
• keyToFreq: key → count
• freqToKeys: count → LinkedHashSet (maintains insertion order for ties)
• minFreq: Tracks the global minimum frequency for eviction.

class LFUCache {
    private final int cap;
    private int minFreq = 0;
    private final Map<Integer, Integer> keyToVal = new HashMap<>();
    private final Map<Integer, Integer> keyToFreq = new HashMap<>();
    private final Map<Integer, LinkedHashSet<Integer>> freqToKeys = new HashMap<>();

    public LFUCache(int capacity) { this.cap = capacity; }

    public int get(int key) {
        if (!keyToVal.containsKey(key)) return -1;
        increaseFreq(key);
        return keyToVal.get(key);
    }

    public void put(int key, int value) {
        if (cap <= 0) return;
        if (keyToVal.containsKey(key)) {
            keyToVal.put(key, value);
            increaseFreq(key);
        } else {
            if (keyToVal.size() >= cap) evictMinFreqKey();
            keyToVal.put(key, value);
            keyToFreq.put(key, 1);
            freqToKeys.computeIfAbsent(1, k -> new LinkedHashSet<>()).add(key);
            minFreq = 1;
        }
    }

    private void increaseFreq(int key) {
        int freq = keyToFreq.get(key);
        keyToFreq.put(key, freq + 1);
        freqToKeys.get(freq).remove(key);
        
        if (freqToKeys.get(freq).isEmpty()) {
            freqToKeys.remove(freq);
            if (minFreq == freq) minFreq++;
        }
        freqToKeys.computeIfAbsent(freq + 1, k -> new LinkedHashSet<>()).add(key);
    }

    private void evictMinFreqKey() {
        LinkedHashSet<Integer> keys = freqToKeys.get(minFreq);
        int evictKey = keys.iterator().next(); // First inserted is the LRU for this frequency
        keys.remove(evictKey);
        
        if (keys.isEmpty()) freqToKeys.remove(minFreq);
        keyToVal.remove(evictKey);
        keyToFreq.remove(evictKey);
    }
}