# LRU Cache

- **Canonical ID**: `lru-cache`
- **Canonical URL**: https://dsacheatsheet.com/problems/lru-cache
- **Difficulty**: medium
- **Patterns**: Linked Lists, Design
- **Version**: 1.0.0 (verified 2026-11-11T21:15:00Z)
- **Original Problem**: https://leetcode.com/problems/lru-cache/

## 1. Core Invariant / The Trick

Combine a HashMap (`key -> Node`) for O(1) lookup with an insertion/recency doubly-linked list (with dummy `head`/`tail` sentinels) so promotion to MRU and eviction from LRU both run in O(1).

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(1)`
- **Space Complexity**: `O(C)`
- **Proof**: Hash lookup + pointer splice at head/tail executes fixed instructions per `get`/`put`; memory is bounded by capacity C.

## 3. Minimal Idiomatic Code

### Python
```python
from collections import OrderedDict
class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache = OrderedDict()

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.cap:
            self.cache.popitem(last=False)
```

### TypeScript
```typescript
export class LRUCache {
  private cap: number;
  private cache = new Map<number, number>();
  constructor(capacity: number) {
    this.cap = capacity;
  }
  get(key: number): number {
    if (!this.cache.has(key)) return -1;
    const val = this.cache.get(key)!;
    this.cache.delete(key);
    this.cache.set(key, val);
    return val;
  }
  put(key: number, value: number): void {
    if (this.cache.has(key)) this.cache.delete(key);
    this.cache.set(key, value);
    if (this.cache.size > this.cap) {
      const oldest = this.cache.keys().next().value!;
      this.cache.delete(oldest);
    }
  }
}
```

### C++
```cpp
class LRUCache {
    int cap;
    list<pair<int,int>> dll;
    unordered_map<int, list<pair<int,int>>::iterator> mp;
public:
    LRUCache(int capacity) : cap(capacity) {}
    int get(int key) {
        auto it = mp.find(key);
        if (it == mp.end()) return -1;
        dll.splice(dll.begin(), dll, it->second);
        return it->second->second;
    }
    void put(int key, int value) {
        if (mp.count(key)) {
            mp[key]->second = value;
            dll.splice(dll.begin(), dll, mp[key]);
            return;
        }
        if ((int)dll.size() == cap) {
            mp.erase(dll.back().first);
            dll.pop_back();
        }
        dll.emplace_front(key, value);
        mp[key] = dll.begin();
    }
};
```

### Java
```java
class LRUCache extends LinkedHashMap<Integer, Integer> {
    private final int cap;
    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);
        this.cap = capacity;
    }
    public int get(int key) { return super.getOrDefault(key, -1); }
    @Override protected boolean removeEldestEntry(Map.Entry<Integer, Integer> e) {
        return size() > cap;
    }
}
```

### Go
```go
type lruNode struct { k, v int; prev, next *lruNode }
type LRUCache struct {
    cap int
    mp  map[int]*lruNode
    h, t *lruNode
}
func Constructor(cap int) LRUCache {
    h, t := &lruNode{}, &lruNode{}
    h.next, t.prev = t, h
    return LRUCache{cap: cap, mp: make(map[int]*lruNode), h: h, t: t}
}
func (c *LRUCache) unlink(n *lruNode) { n.prev.next, n.next.prev = n.next, n.prev }
func (c *LRUCache) addFront(n *lruNode) { n.next, n.prev = c.h.next, c.h; c.h.next.prev, c.h.next = n, n }
func (c *LRUCache) Get(key int) int {
    n, ok := c.mp[key]
    if !ok { return -1 }
    c.unlink(n); c.addFront(n)
    return n.v
}
func (c *LRUCache) Put(key, value int) {
    if n, ok := c.mp[key]; ok { n.v = value; c.unlink(n); c.addFront(n); return }
    if len(c.mp) == c.cap { lru := c.t.prev; c.unlink(lru); delete(c.mp, lru.k) }
    n := &lruNode{k: key, v: value}; c.mp[key] = n; c.addFront(n)
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Updating an existing key in `put` must promote it to MRU and NOT trigger capacity eviction if already present.
- Built-in Map iteration order in JS/Python `OrderedDict` works cleanly too, but interviewers often ask for the manual DLL.

### Follow-ups
- LFU Cache uses frequency buckets (Map of frequency -> doubly-linked list) plus `minFreq` tracking.