460. LFU Cache

At a Glance

Topic: system-design-coding
Pattern: Two-level hash + doubly linked lists per frequency (cousin of 146. LRU Cache — eviction policy differs)
Difficulty: Hard
Companies: Amazon, Google, Meta, Uber, LinkedIn
Frequency: Medium
LeetCode: 460

Problem (one-liner)

Implement an LFU cache: get and put are O(1) average; when eviction is needed, drop the least frequently used key, breaking ties by least recently used among that frequency.

Recognition Cues

Fixed capacity + eviction policy is frequency-first, then recency within frequency
Must match LRU at frequency ties — each frequency bucket is itself an LRU list
Often contrasted with LRU-only — two dimensions (freq × time)

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Priority queue keyed by (freq, time) — heap updates on every touch — O(log n) per op.
Per-key timestamps + full scan — correct policy, not O(1).
Optimal — key -> node map plus frequency -> DLL of nodes (MRU at head, LRU at tail); track minFrequency for eviction list.

Optimal Solution

Data structure layout (read this first)

keyToNode: maps cache key to a live node object that always sits in exactly one frequency list.
frequencyToList: maps frequency f to a doubly linked list of nodes whose current access count is f. Order is MRU near head, LRU near tail (eviction picks tail within the minimum-frequency list).
minFrequency: smallest frequency value that currently has a non-empty list — updated on get/put when the old minimum bucket empties after a promotion.
Eviction on full put (new key): remove the tail of frequencyToList[minFrequency] (LFU, then LRU tie-break).
Promotion: on hit or update, remove node from list f, insert at front of list f+1; if list f becomes empty and f == minFrequency, increment minFrequency.

minFrequency ─────►  [freq=2: A ⇄ B ⇄ C]     [freq=5: X ⇄ Y]
                       ^ MRU          ^ LRU

Go

package main

type cacheNode struct {
	key       int
	value     int
	frequency int
	prev      *cacheNode
	next      *cacheNode
}

type frequencyBucket struct {
	head *cacheNode
	tail *cacheNode
}

func newFrequencyBucket() *frequencyBucket {
	head := &cacheNode{}
	tail := &cacheNode{}
	head.next = tail
	tail.prev = head
	return &frequencyBucket{head: head, tail: tail}
}

func (bucket *frequencyBucket) remove(node *cacheNode) {
	node.prev.next = node.next
	node.next.prev = node.prev
}

func (bucket *frequencyBucket) addToFront(node *cacheNode) {
	node.next = bucket.head.next
	node.prev = bucket.head
	bucket.head.next.prev = node
	bucket.head.next = node
}

func (bucket *frequencyBucket) removeLeastRecentlyUsed() *cacheNode {
	last := bucket.tail.prev
	if last == bucket.head {
		return nil
	}
	bucket.remove(last)
	return last
}

func (bucket *frequencyBucket) isEmpty() bool {
	return bucket.head.next == bucket.tail
}

type LFUCache struct {
	capacity        int
	minFrequency    int // smallest frequency that currently has a nonempty list; bump when that bucket empties after a promotion
	keyToNode       map[int]*cacheNode
	frequencyToList map[int]*frequencyBucket
}

func Constructor(capacity int) LFUCache {
	return LFUCache{
		capacity:        capacity,
		minFrequency:    0,
		keyToNode:       make(map[int]*cacheNode),
		frequencyToList: make(map[int]*frequencyBucket),
	}
}

func (cache *LFUCache) getBucket(freq int) *frequencyBucket {
	if _, exists := cache.frequencyToList[freq]; !exists {
		cache.frequencyToList[freq] = newFrequencyBucket()
	}
	return cache.frequencyToList[freq]
}

func (cache *LFUCache) promote(node *cacheNode) {
	oldFreq := node.frequency
	oldList := cache.frequencyToList[oldFreq]
	oldList.remove(node)
	if oldList.isEmpty() {
		delete(cache.frequencyToList, oldFreq)
		if oldFreq == cache.minFrequency {
			cache.minFrequency++
		}
	}
	node.frequency++
	newList := cache.getBucket(node.frequency)
	newList.addToFront(node)
}

func (cache *LFUCache) Get(key int) int {
	node, exists := cache.keyToNode[key]
	if !exists {
		return -1
	}
	cache.promote(node)
	return node.value
}

func (cache *LFUCache) Put(key int, value int) {
	if cache.capacity == 0 {
		return
	}
	if node, exists := cache.keyToNode[key]; exists {
		node.value = value
		cache.promote(node)
		return
	}
	if len(cache.keyToNode) >= cache.capacity {
		minList := cache.frequencyToList[cache.minFrequency]
		evicted := minList.removeLeastRecentlyUsed()
		if evicted != nil {
			delete(cache.keyToNode, evicted.key)
		}
	}
	newNode := &cacheNode{key: key, value: value, frequency: 1}
	list := cache.getBucket(1)
	list.addToFront(newNode)
	cache.keyToNode[key] = newNode
	cache.minFrequency = 1
}

JavaScript

class DoublyLinkedList {
	constructor() {
		this.head = { prev: null, next: null };
		this.tail = { prev: null, next: null };
		this.head.next = this.tail;
		this.tail.prev = this.head;
	}

	remove(node) {
		node.prev.next = node.next;
		node.next.prev = node.prev;
	}

	addToFront(node) {
		node.next = this.head.next;
		node.prev = this.head;
		this.head.next.prev = node;
		this.head.next = node;
	}

	removeLeastRecentlyUsed() {
		const last = this.tail.prev;
		if (last === this.head) {
			return null;
		}
		this.remove(last);
		return last;
	}

	isEmpty() {
		return this.head.next === this.tail;
	}
}

/**
 * @param {number} capacity
 */
var LFUCache = function (capacity) {
	this.capacity = capacity;
	// minFrequency: smallest frequency with a nonempty bucket; advanced when the min bucket goes empty after get/put promote
	this.minFrequency = 0;
	this.keyToNode = new Map();
	this.frequencyToList = new Map();
};

LFUCache.prototype._getBucket = function (frequency) {
	if (!this.frequencyToList.has(frequency)) {
		this.frequencyToList.set(frequency, new DoublyLinkedList());
	}
	return this.frequencyToList.get(frequency);
};

LFUCache.prototype._promote = function (node) {
	const oldFreq = node.frequency;
	const oldList = this.frequencyToList.get(oldFreq);
	oldList.remove(node);
	if (oldList.isEmpty()) {
		this.frequencyToList.delete(oldFreq);
		if (oldFreq === this.minFrequency) {
			this.minFrequency += 1;
		}
	}
	node.frequency += 1;
	const newList = this._getBucket(node.frequency);
	newList.addToFront(node);
};

/**
 * @param {number} key
 * @return {number}
 */
LFUCache.prototype.get = function (key) {
	const node = this.keyToNode.get(key);
	if (!node) {
		return -1;
	}
	this._promote(node);
	return node.value;
};

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
LFUCache.prototype.put = function (key, value) {
	if (this.capacity === 0) {
		return;
	}
	if (this.keyToNode.has(key)) {
		const node = this.keyToNode.get(key);
		node.value = value;
		this._promote(node);
		return;
	}
	if (this.keyToNode.size >= this.capacity) {
		const minList = this.frequencyToList.get(this.minFrequency);
		const evicted = minList.removeLeastRecentlyUsed();
		if (evicted) {
			this.keyToNode.delete(evicted.key);
		}
	}
	const newNode = { key, value, frequency: 1, prev: null, next: null };
	const list = this._getBucket(1);
	list.addToFront(newNode);
	this.keyToNode.set(key, newNode);
	this.minFrequency = 1;
};

Capacity 2. put(1,1), put(2,2): both at freq 1, minFrequency=1. get(1): key 1 moves to freq 2; freq 1 list only has key 2, still minFrequency=1. put(3,3) evicts LRU from freq 1 → removes key 2. Invariant: each key sits in exactly one frequency list; minFrequency always points at a nonempty bucket when cache is nonempty.

Edge Cases

capacity == 0 — every put is no-op or immediate miss per problem contract
Repeated get on same key — frequency climbs; eviction pool shrinks at low frequencies
Tie-breaking — two keys at freq 1: evict the one touched longer ago (tail of that list)
Update put on existing key — refresh value and count as use (promote frequency)

Pitfalls

Evicting from wrong frequency list (must be minFrequency, not global LRU across all keys)
Forgetting to bump minFrequency when the current minimum bucket empties after a promotion
Inserting a new key after eviction without resetting minFrequency to 1

Variants

TTL per key — decay frequency over wall-clock time or expire entries in background sweeps
Approximate LFU — windowed counts (TinyLFU) for massive caches where exact structures are heavy
Shard by hash — parallelize LFU structures per partition for multicore cache lines

Mind-Map Tags

#lfu #doubly-linked-list #hash-map #frequency-buckets #min-frequency-pointer #eviction-policy