LeetCode 460 - LFU Cache

The problem asks us to design a cache that supports two operations: - get(key) returns the value associated with a key if it exists, otherwise -1 - put(key, value) inserts or updates a key-value pair Unlike a normal cache, eviction is not based only on recency.

leetcodehardhash-tablelinked-listdesigndoubly-linked-list

LeetCode Problem 460

Difficulty: 🔴 Hard
Topics: Hash Table, Linked List, Design, Doubly-Linked List

Solution

Problem Understanding

The problem asks us to design a cache that supports two operations:

  • get(key) returns the value associated with a key if it exists, otherwise -1
  • put(key, value) inserts or updates a key-value pair

Unlike a normal cache, eviction is not based only on recency. Instead, this cache uses the Least Frequently Used policy.

Every key maintains a frequency counter:

  • A newly inserted key starts with frequency 1
  • Every successful get
  • Every update through put

increments that frequency

When the cache becomes full and a new key must be inserted, we remove the key with the smallest frequency.

If multiple keys share the same minimum frequency, we break ties using Least Recently Used ordering. Among keys with equal frequency, the oldest one is removed.

The biggest challenge is the performance requirement. Both get and put must run in O(1) average time complexity.

The constraints are large enough that any linear scan approach will fail:

  • Capacity can be up to 10^4
  • Up to 2 * 10^5 operations are performed

This means we cannot repeatedly search through all keys to find the least frequently used item.

A correct solution must efficiently support:

  1. Looking up a key quickly
  2. Updating its frequency quickly
  3. Finding the minimum frequency quickly
  4. Removing the least recently used key among equal frequencies quickly

Several edge cases are important:

  • Capacity can be zero
  • Updating an existing key should increase frequency
  • Multiple keys may share the same frequency
  • The minimum frequency changes dynamically as keys are updated
  • A frequency list may become empty after moving nodes

These details make the implementation significantly more complex than a standard LRU cache.

Approaches

Brute Force Approach

A straightforward implementation would store all cache entries in a hash map and maintain a frequency counter for each key.

For every get or put, we update the corresponding frequency.

When eviction is needed, we scan through all keys to find:

  1. The minimum frequency
  2. Among those keys, the least recently used one

This approach is correct because we explicitly compute the eviction candidate every time.

However, the eviction step becomes expensive. In the worst case, we may scan all keys inside every put operation. Since the cache can contain up to 10^4 elements and there can be 2 * 10^5 operations, this becomes too slow.

Optimal Approach

The key insight is that we need two levels of organization:

  1. Fast lookup by key
  2. Fast grouping by frequency

We combine:

  • A hash map from key to node
  • A hash map from frequency to doubly linked list

Each frequency owns its own LRU list.

For example:

  • Frequency 1 has a doubly linked list
  • Frequency 2 has another list
  • Frequency 3 has another list

Within each frequency list:

  • Most recently used nodes are near the front
  • Least recently used nodes are near the back

This structure allows us to:

  • Move nodes between frequency lists in O(1)
  • Remove the LRU node from the minimum frequency list in O(1)
  • Update frequencies in O(1)

We also maintain a global min_freq variable so we always know the current minimum frequency.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) per eviction O(n) Scans all keys to find LFU/LRU candidate
Optimal O(1) average per operation O(n) Uses hash maps plus frequency-based doubly linked lists

Algorithm Walkthrough

Data Structures

We maintain four important components:

  1. A Node object storing:
  • key
  • value
  • frequency
  • previous pointer
  • next pointer
  1. A hash map:
  • key_to_node[key] -> node
  1. A hash map:
  • freq_to_list[freq] -> doubly linked list
  1. A variable:
  • min_freq

Each doubly linked list stores nodes with the same frequency in LRU order.

Step-by-Step Algorithm

  1. Initialize the cache with a fixed capacity.

We create:

  • an empty key-to-node map
  • an empty frequency-to-list map
  • min_freq = 0
  1. For get(key):

First check whether the key exists in the cache.

If not found, return -1.

Otherwise:

  • retrieve the node
  • increase its frequency
  • move it from its old frequency list to the new frequency list
  • return its value
  1. To increase a node's frequency:

Suppose the node currently has frequency f.

We:

  • remove it from frequency list f
  • if that list becomes empty and f == min_freq, increment min_freq
  • increase node frequency to f + 1
  • insert the node into frequency list f + 1
  1. For put(key, value):

If capacity is zero, do nothing. 5. If the key already exists:

We:

  • update the node value
  • treat this as an access
  • increase its frequency
  1. If the key does not exist and cache is full:

We must evict.

The eviction candidate is:

  • the least recently used node
  • from the list with frequency min_freq

Since the list is maintained in LRU order:

  • the node near the tail is removed
  1. After eviction:

We create a new node:

  • frequency starts at 1

Then:

  • insert it into frequency list 1
  • add it to the key map
  • set min_freq = 1

Why it works

The algorithm maintains two invariants:

  1. Every frequency list contains only nodes with that exact frequency.
  2. Within a frequency list, nodes are ordered by recency.

Because min_freq always tracks the smallest existing frequency, eviction always chooses from the correct frequency group.

Because each frequency list is maintained in LRU order, removing the least recently used node within that group is also correct.

Together, these invariants guarantee that eviction always follows the LFU rule with LRU tie-breaking.

Python Solution

from collections import defaultdict
from typing import Optional

class Node:
    def __init__(self, key: int, value: int):
        self.key = key
        self.value = value
        self.freq = 1

        self.prev: Optional["Node"] = None
        self.next: Optional["Node"] = None

class DoublyLinkedList:
    def __init__(self):
        self.head = Node(0, 0)
        self.tail = Node(0, 0)

        self.head.next = self.tail
        self.tail.prev = self.head

        self.size = 0

    def add_front(self, node: Node) -> None:
        node.next = self.head.next
        node.prev = self.head

        self.head.next.prev = node
        self.head.next = node

        self.size += 1

    def remove(self, node: Node) -> None:
        prev_node = node.prev
        next_node = node.next

        prev_node.next = next_node
        next_node.prev = prev_node

        self.size -= 1

    def remove_last(self) -> Node:
        if self.size == 0:
            return None

        last_node = self.tail.prev
        self.remove(last_node)

        return last_node

class LFUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.min_freq = 0

        self.key_to_node = {}
        self.freq_to_list = defaultdict(DoublyLinkedList)

    def _update_frequency(self, node: Node) -> None:
        old_freq = node.freq

        old_list = self.freq_to_list[old_freq]
        old_list.remove(node)

        if old_freq == self.min_freq and old_list.size == 0:
            self.min_freq += 1

        node.freq += 1

        new_list = self.freq_to_list[node.freq]
        new_list.add_front(node)

    def get(self, key: int) -> int:
        if key not in self.key_to_node:
            return -1

        node = self.key_to_node[key]
        self._update_frequency(node)

        return node.value

    def put(self, key: int, value: int) -> None:
        if self.capacity == 0:
            return

        if key in self.key_to_node:
            node = self.key_to_node[key]
            node.value = value

            self._update_frequency(node)
            return

        if len(self.key_to_node) == self.capacity:
            lfu_list = self.freq_to_list[self.min_freq]

            node_to_remove = lfu_list.remove_last()

            del self.key_to_node[node_to_remove.key]

        new_node = Node(key, value)

        self.key_to_node[key] = new_node

        freq_list = self.freq_to_list[1]
        freq_list.add_front(new_node)

        self.min_freq = 1

The implementation uses a custom doubly linked list because Python's built-in structures do not support arbitrary node removal in O(1) time.

Each frequency has its own doubly linked list. Nodes move between these lists whenever their access frequency changes.

The _update_frequency helper centralizes all frequency update logic. This prevents duplicated code between get and put.

The min_freq variable is especially important. Without it, we would need to scan frequencies to determine the eviction target, which would violate the O(1) requirement.

The doubly linked list stores nodes in recency order:

  • Front = most recently used
  • Back = least recently used

This allows efficient LFU plus LRU tie-breaking.

Go Solution

package main

type Node struct {
	key   int
	value int
	freq  int

	prev *Node
	next *Node
}

type DoublyLinkedList struct {
	head *Node
	tail *Node
	size int
}

func NewDoublyLinkedList() *DoublyLinkedList {
	head := &Node{}
	tail := &Node{}

	head.next = tail
	tail.prev = head

	return &DoublyLinkedList{
		head: head,
		tail: tail,
	}
}

func (dll *DoublyLinkedList) AddFront(node *Node) {
	node.next = dll.head.next
	node.prev = dll.head

	dll.head.next.prev = node
	dll.head.next = node

	dll.size++
}

func (dll *DoublyLinkedList) Remove(node *Node) {
	prevNode := node.prev
	nextNode := node.next

	prevNode.next = nextNode
	nextNode.prev = prevNode

	dll.size--
}

func (dll *DoublyLinkedList) RemoveLast() *Node {
	if dll.size == 0 {
		return nil
	}

	lastNode := dll.tail.prev
	dll.Remove(lastNode)

	return lastNode
}

type LFUCache struct {
	capacity  int
	minFreq   int
	keyToNode map[int]*Node
	freqToList map[int]*DoublyLinkedList
}

func Constructor(capacity int) LFUCache {
	return LFUCache{
		capacity:  capacity,
		minFreq:   0,
		keyToNode: make(map[int]*Node),
		freqToList: make(map[int]*DoublyLinkedList),
	}
}

func (this *LFUCache) updateFrequency(node *Node) {
	oldFreq := node.freq

	oldList := this.freqToList[oldFreq]
	oldList.Remove(node)

	if oldFreq == this.minFreq && oldList.size == 0 {
		this.minFreq++
	}

	node.freq++

	if _, exists := this.freqToList[node.freq]; !exists {
		this.freqToList[node.freq] = NewDoublyLinkedList()
	}

	newList := this.freqToList[node.freq]
	newList.AddFront(node)
}

func (this *LFUCache) Get(key int) int {
	node, exists := this.keyToNode[key]

	if !exists {
		return -1
	}

	this.updateFrequency(node)

	return node.value
}

func (this *LFUCache) Put(key int, value int) {
	if this.capacity == 0 {
		return
	}

	if node, exists := this.keyToNode[key]; exists {
		node.value = value
		this.updateFrequency(node)
		return
	}

	if len(this.keyToNode) == this.capacity {
		lfuList := this.freqToList[this.minFreq]

		nodeToRemove := lfuList.RemoveLast()

		delete(this.keyToNode, nodeToRemove.key)
	}

	newNode := &Node{
		key:   key,
		value: value,
		freq:  1,
	}

	if _, exists := this.freqToList[1]; !exists {
		this.freqToList[1] = NewDoublyLinkedList()
	}

	this.freqToList[1].AddFront(newNode)

	this.keyToNode[key] = newNode
	this.minFreq = 1
}

/**
 * Your LFUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */

The Go implementation follows the same overall design as the Python version.

One important difference is explicit pointer handling. Go does not provide built-in nullable object references in the same way Python does, so all linked list operations use pointers directly.

The frequency lists are lazily initialized using make(map[int]*DoublyLinkedList) and conditional creation.

Go integers are large enough for the given constraints, so overflow is not a concern here.

Worked Examples

Example 1

capacity = 2
Operation Cache State Frequencies Explanation
put(1,1) [1] 1->freq1 Insert key 1
put(2,2) [2,1] 1->freq1, 2->freq1 Most recent at front
get(1) [1],[2] 1->freq2, 2->freq1 Key 1 frequency increases
put(3,3) [3],[1] 3->freq1, 1->freq2 Evict key 2
get(2) unchanged unchanged Return -1
get(3) [3,1] 3->freq2, 1->freq2 Key 3 frequency increases
put(4,4) [4],[3] 4->freq1, 3->freq2 Evict key 1
get(1) unchanged unchanged Return -1
get(3) [3],[4] 3->freq3, 4->freq1 Frequency updated
get(4) [4],[3] 4->freq2, 3->freq3 Frequency updated

Detailed state after major operations:

After put(1,1)

Frequency LRU Order
1 [1]

min_freq = 1

After put(2,2)

Frequency LRU Order
1 [2,1]

2 is most recent.

After get(1)

Frequency LRU Order
1 [2]
2 [1]

min_freq = 1

After put(3,3)

Key 2 is evicted because:

  • frequency 1 is smallest
  • among frequency 1, key 2 is LRU
Frequency LRU Order
1 [3]
2 [1]

After put(4,4)

Keys 1 and 3 both have frequency 2.

LRU tie-breaker removes key 1.

Frequency LRU Order
1 [4]
2 [3]

Complexity Analysis

Measure Complexity Explanation
Time O(1) average All hash map and linked list operations are constant time
Space O(capacity) We store nodes plus frequency lists

Every operation performs only:

  • hash map lookups
  • linked list insertions
  • linked list removals

Each of these operations is constant time.

No scanning or sorting occurs, which is why the solution satisfies the strict performance requirement.

Test Cases

# Provided example
cache = LFUCache(2)

cache.put(1, 1)
cache.put(2, 2)

assert cache.get(1) == 1  # frequency of key 1 becomes 2

cache.put(3, 3)  # evicts key 2

assert cache.get(2) == -1  # key 2 removed
assert cache.get(3) == 3   # key 3 exists

cache.put(4, 4)  # evicts key 1

assert cache.get(1) == -1  # key 1 removed
assert cache.get(3) == 3   # key 3 still exists
assert cache.get(4) == 4   # key 4 exists

# Capacity zero
cache = LFUCache(0)

cache.put(1, 1)

assert cache.get(1) == -1  # nothing stored

# Update existing key
cache = LFUCache(2)

cache.put(1, 1)
cache.put(1, 10)

assert cache.get(1) == 10  # value updated

# LRU tie breaker
cache = LFUCache(2)

cache.put(1, 1)
cache.put(2, 2)

cache.get(1)
cache.get(2)

cache.put(3, 3)

assert cache.get(1) == -1  # key 1 older among same frequency
assert cache.get(2) == 2
assert cache.get(3) == 3

# Repeated frequency updates
cache = LFUCache(2)

cache.put(1, 1)

for _ in range(10):
    cache.get(1)

cache.put(2, 2)
cache.put(3, 3)

assert cache.get(1) == 1   # highly frequent key survives
assert cache.get(2) == -1  # lower frequency evicted
assert cache.get(3) == 3

# Single capacity
cache = LFUCache(1)

cache.put(1, 1)
cache.put(2, 2)

assert cache.get(1) == -1  # replaced
assert cache.get(2) == 2
Test Why
Provided example Validates LFU and LRU behavior together
Capacity zero Ensures no insertion occurs
Update existing key Confirms updates also increase frequency
LRU tie breaker Verifies correct tie resolution
Repeated frequency updates Ensures highly used keys survive eviction
Single capacity Tests smallest non-zero cache

Edge Cases

Capacity Equals Zero

If capacity is zero, the cache cannot store anything. This case is easy to overlook because insertion logic may still try to allocate nodes or evict entries.

The implementation handles this immediately at the start of put:

if self.capacity == 0:
    return

This guarantees the cache always remains empty.

Updating an Existing Key

When put(key, value) is called for an existing key, the operation counts as usage and must increase the frequency.

A common bug is updating the value without adjusting frequency.

The implementation avoids this by calling _update_frequency(node) after updating the value.

Multiple Keys With Same Frequency

The hardest part of the problem is tie-breaking.

Suppose several keys all have frequency 2. We must evict the least recently used among them.

A naive implementation might accidentally evict the wrong key if recency ordering is not maintained carefully.

The doubly linked list solves this by storing keys in exact usage order:

  • front = most recent
  • back = least recent

Eviction always removes from the tail of the minimum-frequency list, guaranteeing correct LRU behavior.

Frequency List Becoming Empty

Another subtle issue occurs when moving a node out of the current minimum-frequency list.

If that list becomes empty, min_freq must increase.

Failing to update min_freq causes future evictions to target an empty list.

The implementation checks:

if old_freq == self.min_freq and old_list.size == 0:
    self.min_freq += 1

This ensures min_freq always points to a valid frequency group.