13.1 Design LRU Cache

13.1.1 Problem Metadata

13.1.2 Description

Implement a Least Recently Used (LRU) cache that supports constant-time get(key) and put(key, value) operations. When the cache reaches capacity it must evict the least recently used entry before inserting a new one.

13.1.3 Examples

LRUCache cache = new LRUCache(2);
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 1
cache.put(3, 3); // evicts key 2
cache.get(2); // -1
cache.put(4, 4); // evicts key 1
cache.get(1); // -1
cache.get(3); // 3
cache.get(4); // 4

13.1.4 Constraints

  • 1 <= capacity <= 3000
  • -10^4 <= key, value <= 10^4
  • At most 10^5 operations

13.1.5 Solution 1 - Hash Map + Doubly Linked List

13.1.5.1 Walkthrough

Store key-to-node mappings in a hash map, while nodes form a doubly linked lc-list ordered by recency. The head is most recent, tail is least recent. get moves the node to the head. put updates existing keys similarly or inserts a new node at the head and, if over capacity, removes the tail node and deletes it from the map. Sentinel head/tail nodes simplify pointer updates.

13.1.5.2 Pointer Diagrams

The diagrams below show how the doubly linked list pointers change for each helper. H and T are sentinel nodes. X is the node we are moving or removing.

addAfterHead(X)

Before:
H <-> A <-> ... <-> T

Step 1: X hooks forward
H <-> A <-> ... <-> T
|\
| X -> A (X.next = a)
|
(X.prev = H)

Step 2: neighbors point back to X
H <-> X <-> A <-> ... <-> T

remove(X)

Before:
... <-> P <-> X <-> N <-> ...

Step 1: bypass X forward (P.next = X.next)
... <-> P ----> N <-> ...

Step 2: bypass X backward (N.prev = X.prev)
... <-> P <---- N <-> ...

After:
... <-> P <-> N <-> ...

moveToHead(X) = remove(X) + addAfterHead(X)

Before:
H <-> A <-> ... <-> P <-> X <-> N <-> ... <-> T

Step 1: remove(X)
H <-> A <-> ... <-> P <-> N <-> ... <-> T

Step 2: addAfterHead(X)
H <-> X <-> A <-> ... <-> P <-> N <-> ... <-> T

13.1.5.3 Analysis

  • Time Complexity: O(1) per operation
  • Space Complexity: O(capacity)

13.1.5.4 Implementation Steps

  1. Maintain Map<Integer, Node> cache and sentinel head, tail.
  2. get(key):
    • If key missing return -1.
    • Move node to head and return value.
  3. put(key, value):
    • If key exists, update value and move node to head.
    • Otherwise create new node at head and insert into map.
    • If size exceeds capacity remove tail predecessor and delete from map.

13.1.5.5 Code - Java

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

    private final Map<Integer, Node> cache = new HashMap<>();
    // dummy head; real head is dummyHead.next
    private final Node dummyHead = new Node(0, 0);
    // dummy tail; real tail is dummyTail.prev
    private final Node dummyTail = new Node(0, 0);
    private final int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        dummyHead.next = dummyTail;
        dummyTail.prev = dummyHead;
    }

    public int get(int key) {
        Node node = cache.get(key);
        if (node == null) {
            return -1;
        }
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        Node node = cache.get(key);
        if (node != null) {
            node.value = value;
            moveToHead(node);
            return;
        }
        Node fresh = new Node(key, value);
        cache.put(key, fresh);
        addAfterHead(fresh);
        if (cache.size() > capacity) {
            Node lru = dummyTail.prev;
            remove(lru);
            cache.remove(lru.key);
        }
    }

    private void moveToHead(Node node) {
        remove(node);
        addAfterHead(node);
    }

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

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

13.1.5.6 Code - Go

type node struct {
    key, value int
    prev, next *node
}

type LRUCache struct {
    capacity  int
    cache     map[int]*node
    dummyHead *node // dummy head; real head is dummyHead.next
    dummyTail *node // dummy tail; real tail is dummyTail.prev
}

func Constructor(capacity int) LRUCache {
    head := &node{}
    tail := &node{}
    head.next = tail
    tail.prev = head
    return LRUCache{
        capacity:  capacity,
        cache:     make(map[int]*node),
        dummyHead: head,
        dummyTail: tail,
    }
}

func (this *LRUCache) Get(key int) int {
    if n, ok := this.cache[key]; ok {
        this.moveToHead(n)
        return n.value
    }
    return -1
}

func (this *LRUCache) Put(key int, value int) {
    if n, ok := this.cache[key]; ok {
        n.value = value
        this.moveToHead(n)
        return
    }

    n := &node{key: key, value: value}
    this.cache[key] = n
    this.addAfterHead(n)
    if len(this.cache) > this.capacity {
        lru := this.dummyTail.prev
        this.remove(lru)
        delete(this.cache, lru.key)
    }
}

func (this *LRUCache) moveToHead(n *node) {
    this.remove(n)
    this.addAfterHead(n)
}

func (this *LRUCache) addAfterHead(n *node) {
    n.next = this.dummyHead.next
    n.prev = this.dummyHead
    this.dummyHead.next.prev = n
    this.dummyHead.next = n
}

func (this *LRUCache) remove(n *node) {
    n.prev.next = n.next
    n.next.prev = n.prev
}

13.1.6 Solution 2 - LinkedHashMap

13.1.6.1 Walkthrough

Java’s LinkedHashMap already maintains access order. Extend it and override removeEldestEntry to delete the oldest entry when size exceeds capacity. Calls to get and put become thin wrappers around the standard map operations.

13.1.6.2 Analysis

  • Time Complexity: O(1) expected per operation
  • Space Complexity: O(capacity)

13.1.6.3 Implementation Steps

  1. Extend LinkedHashMap<Integer, Integer> with accessOrder flag set to true.
  2. Define removeEldestEntry to compare size with capacity.
  3. Delegate get/put to underlying map.

13.1.6.4 Code - Java

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

    public LRUCacheLinkedHashMap(int capacity) {
        this.capacity = capacity;
        this.map = new LinkedHashMap<>(capacity, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
                return size() > LRUCacheLinkedHashMap.this.capacity;
            }
        };
    }

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

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