460. LFU Cache

HardDesignHash TableLinked ListDoubly-Linked List

Problem Description

In this problem, we need to design a Least Frequently Used (LFU) cache. An LFU cache is a type of cache that removes the least frequently accessed item when it needs space. If there are multiple items with the same lowest frequency, it removes the least recently used among those.

The LFUCache class requires the following operations:

LFUCache(int capacity): Constructor that initializes the cache with a given capacity.
int get(int key): Retrieves the value linked to the key from the cache. If the key is not present, it should return -1.
void put(int key, int value): Inserts or updates the value of the key. If inserting a new item causes the cache to exceed its capacity, the least frequently used key should be removed. In case of a tie (when multiple keys have the same frequency), the least recently used key should be removed.

Additionally, each key in the cache will have a use counter which increments every time the key is accessed through get or put operations. The goal is to implement get and put methods that each run with an average time complexity of O(1).

Intuition

The solution to this problem requires us to perform insertion, access, and removal operations with O(1) complexity. We can satisfy these requirements with a combination of data structures: hashtables and doubly linked lists.

Hashtable: Allows O(1) access to nodes by their keys.
Doubly Linked Lists: Allow O(1) insertion and removal of nodes. We use one doubly linked list per frequency count, so each list contains all nodes that have been accessed a certain number of times.

For the LFUCache, we maintain the following:

A map that maps keys to their corresponding node which contains the value and frequency of access.
A freq_map that maps frequencies to a doubly linked list containing all nodes with that frequency.
A variable min_freq to keep track of the minimum frequency of all keys in the cache for easy access to the least frequently used item.

When a get or put operation is called, we update the corresponding node's frequency, move it to the respective frequency list in the freq_map, and update min_freq if necessary. If a put operation is performed on a full cache, we remove the least frequently used item. When there's a tie, we remove the least recently used item from the list corresponding to the lowest frequency.

By doing this, we ensure constant-time O(1) complexity for get and put operations while maintaining the structure of the LFU cache.

Learn more about Linked List patterns.

Solution Approach

The implementation for the LFU Cache problem involves designing a set of classes to efficiently manage our cache operations. Here we will discuss the algorithms, patterns, and data structures utilized in the solution code provided:

Node Class

A Node represents an item in the cache, with properties for its key, value, frequency (freq), prev (previous node), and next (next node). This will be used to store each entry and will be inserted into a doubly linked list.

DoublyLinkedList Class

A DoublyLinkedList is used to keep track of all items with the same frequency. It supports adding a node to the head (add_first), removing a specific node (remove), and removing the last node (remove_last). An empty list can be checked with is_empty.

LFUCache Class

Data Structures:

self.map: A dictionary (hashtable) to map keys to their corresponding node (Node objects).
self.freq_map: A dictionary to map frequencies to their corresponding doubly linked list, where each list contains all nodes with that frequency.
self.min_freq: An integer tracking the current minimum frequency amongst all keys in the cache.

Constructor:

Initializes the data structures and sets the capacity of the cache.

get Method:

Retrieves the node from the map using the given key.
If the key is missing or the capacity is 0, returns -1.
If the node is found, it calls the incr_freq method to update the frequency of the node and returns its value.

put Method:

If the capacity is 0, the function ends early as no items can be put into the cache.
If the key is present in the map, it updates the value in the corresponding node and increases the frequency by calling incr_freq.
If the key is not present and the cache is at full capacity, it removes the least frequently used item by (1) accessing the linked list for the current minimum frequency, (2) removing the last node from that list, and (3) removing the node's key from the map.
A new node is created and added to the map and to the frequency map under frequency 1. The min_freq is set to 1.

incr_freq Method:

Removes the node from its current frequency list in freq_map.
If the removal of the node results in an empty list and that frequency was the min_freq, increments min_freq.
Increments the node's frequency, inserts it into the linked list in the freq_map that corresponds to the new frequency.

add_node Method:

A helper used to add a node to the linked list in the freq_map corresponding to the node’s frequency.

With these components combined, we ensure each operation on the cache is O(1) on average by efficiently tracking both the least frequently and least recently used items.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's say we have an LFU Cache with a capacity of 2, and we perform the following operations:

put(1, 10): The cache is empty, so this will create a new node with key 1 and value 10. The frequency is set to 1. Our frequency map has 1 -> Node(1) and min_freq is now 1.
put(2, 20): A new node with key 2 and value 20 is created. Similar to the first step, this node's frequency is also 1 and is added to the same frequency list. The frequency map now is 1 -> Node(1) <-> Node(2).
get(1): This operation will get the node with key 1, which has a value of 10. The frequency of this node will be incremented to 2. Since it's the only node with this frequency, it will be added to a new frequency list. The frequency map updates to 1 -> Node(2) and 2 -> Node(1). min_freq remains 1.
put(3, 30): We need to add a new node with key 3 and value 30. Since the cache has reached its capacity, we must remove an item. We look at min_freq which is 1 and remove the least recently used item from that frequency's list, which is Node(2). We then add Node(3) with a frequency of 1 to the list. The frequency map is now 1 -> Node(3) and 2 -> Node(1).
get(3): The node with key 3 is accessed, increasing its frequency to 2. Now both nodes with keys 1 and 3 have the same frequency. The lists are updated: 1 -> becomes empty and 2 -> Node(1) <-> Node(3). min_freq is updated to 2 because there are no nodes with a frequency of 1 after this operation.
get(1): The node with key 1 is accessed again, so its frequency increases to 3. We update the lists such that 2 -> Node(3) and a new list 3 -> Node(1) is created. min_freq remains 2.

The sequence of operations above demonstrates how the LFU Cache responds to different commands. The cache maintains the frequency of each node with the help of the freq_map, and updates the min_freq accordingly to ensure that the least frequently and least recently used node is always easily identifiable and removable in constant time.

Solution Implementation

1from collections import defaultdict
2
3class Node:
4    def __init__(self, key: int, value: int) -> None:
5        self.key = key
6        self.value = value
7        self.freq = 1
8        self.prev = None
9        self.next = None
10
11
12class DoublyLinkedList:
13    def __init__(self) -> None:
14        self.head = Node(-1, -1)  # Sentinel head node
15        self.tail = Node(-1, -1)  # Sentinel tail node
16        self.head.next = self.tail
17        self.tail.prev = self.head
18
19    def add_first(self, node: Node) -> None:
20        """Add a node right after the head."""
21        node.prev = self.head
22        node.next = self.head.next
23        self.head.next.prev = node
24        self.head.next = node
25
26    def remove(self, node: Node) -> Node:
27        """Remove an existing node from the list."""
28        node.prev.next = node.next
29        node.next.prev = node.prev
30        # Clear the removed node's pointers
31        node.next, node.prev = None, None
32        return node
33
34    def remove_last(self) -> Node:
35        """Remove the last node and return it."""
36        return self.remove(self.tail.prev)
37
38    def is_empty(self) -> bool:
39        """Check if the list is empty."""
40        return self.head.next == self.tail
41
42
43class LFUCache:
44    def __init__(self, capacity: int):
45        self.capacity = capacity
46        self.min_freq = 0
47        self.key_node_map = defaultdict(Node)
48        self.freq_node_list_map = defaultdict(DoublyLinkedList)
49
50    def get(self, key: int) -> int:
51        """Get the value of the key if the key exists in the cache."""
52        if self.capacity == 0 or key not in self.key_node_map:
53            return -1
54
55        node = self.key_node_map[key]
56        self._increase_freq(node)
57        return node.value
58
59    def put(self, key: int, value: int) -> None:
60        """Set or insert the value if the key is not already present."""
61        if self.capacity == 0:
62            return
63
64        if key in self.key_node_map:
65            node = self.key_node_map[key]
66            node.value = value
67            self._increase_freq(node)
68            return
69
70        if len(self.key_node_map) == self.capacity:
71            least_freq_list = self.freq_node_list_map[self.min_freq]
72            node_to_remove = least_freq_list.remove_last()
73            del self.key_node_map[node_to_remove.key]
74
75        new_node = Node(key, value)
76        self._add_node(new_node)
77        self.key_node_map[key] = new_node
78        self.min_freq = 1  # Reset min_freq to 1 as a new node is added
79
80    def _increase_freq(self, node: Node) -> None:
81        """Increase the frequency count of a node."""
82        freq = node.freq
83        node_list = self.freq_node_list_map[freq]
84        node_list.remove(node)
85        if node_list.is_empty():
86            del self.freq_node_list_map[freq]
87            if freq == self.min_freq:
88                self.min_freq += 1
89
90        node.freq += 1
91        self._add_node(node)
92
93    def _add_node(self, node: Node) -> None:
94        """Add a node to the list that corresponds to its frequency count."""
95        freq = node.freq
96        node_list = self.freq_node_list_map[freq]
97        node_list.add_first(node)
98      
99# Example of how to use LFUCache:
100# cache = LFUCache(capacity)
101# value = cache.get(key)
102# cache.put(key, value)
103

1import java.util.HashMap;
2import java.util.Map;
3
4class LFUCache {
5
6    private final Map<Integer, Node> cache; // The map to store the key-node pairs
7    private final Map<Integer, DoublyLinkedList> frequencyMap; // The map to store the frequency-node list pairs
8    private final int capacity; // The capacity of the LFU cache
9    private int minimumFrequency; // The current minimum frequency of the nodes in the cache
10
11    public LFUCache(int capacity) {
12        this.capacity = capacity;
13        cache = new HashMap<>();
14        frequencyMap = new HashMap<>();
15    }
16
17    public int get(int key) {
18        if (capacity == 0) {
19            return -1;
20        }
21        if (!cache.containsKey(key)) {
22            return -1;
23        }
24
25        // get the node and increment its frequency
26        Node node = cache.get(key);
27        increaseFrequency(node);
28        return node.value;
29    }
30
31    public void put(int key, int value) {
32        if (capacity == 0) {
33            return;
34        }
35        if (cache.containsKey(key)) {
36            // update the value and frequency of the existing node
37            Node node = cache.get(key);
38            node.value = value;
39            increaseFrequency(node);
40            return;
41        }
42        if (cache.size() == capacity) {
43            // evict the least frequently used node, choosing the least recently used one if there's a tie
44            DoublyLinkedList leastFreqList = frequencyMap.get(minimumFrequency);
45            Node toRemove = leastFreqList.removeLast();
46            cache.remove(toRemove.key);
47        }
48        // create a new node and add it to the cache and frequency map
49        Node newNode = new Node(key, value);
50        addNodeToFrequencyList(newNode);
51        cache.put(key, newNode);
52        minimumFrequency = 1; // reset the minimum frequency
53    }
54
55    private void increaseFrequency(Node node) {
56        int currentFrequency = node.frequency;
57        DoublyLinkedList currentList = frequencyMap.get(currentFrequency);
58        currentList.remove(node);
59        if (currentList.isEmpty()) {
60            frequencyMap.remove(currentFrequency);
61            if (currentFrequency == minimumFrequency) {
62                minimumFrequency++; // increment the minimum frequency if necessary
63            }
64        }
65        node.frequency++;
66        addNodeToFrequencyList(node);
67    }
68
69    private void addNodeToFrequencyList(Node node) {
70        // add the node to the new frequency's list or create a new list if it does not exist
71        int newFrequency = node.frequency;
72        DoublyLinkedList newList = frequencyMap.getOrDefault(newFrequency, new DoublyLinkedList());
73        newList.addFirst(node);
74        frequencyMap.put(newFrequency, newList);
75    }
76
77    private static class Node {
78        int key;
79        int value;
80        int frequency; // the frequency of accesses to this node
81        Node prev;
82        Node next;
83
84        Node(int key, int value) {
85            this.key = key;
86            this.value = value;
87            frequency = 1; // initially, all nodes have frequency 1
88        }
89    }
90
91    private static class DoublyLinkedList {
92        // dummy head and tail make it easier to add/remove nodes
93        private final Node head;
94        private final Node tail;
95
96        public DoublyLinkedList() {
97            head = new Node(-1, -1);
98            tail = new Node(-1, -1);
99            head.next = tail;
100            tail.prev = head;
101        }
102
103        public void addFirst(Node node) {
104            // add a new node right after the dummy head
105            node.prev = head;
106            node.next = head.next;
107            head.next.prev = node;
108            head.next = node;
109        }
110
111        public Node remove(Node node) {
112            // remove a node from its current position
113            node.prev.next = node.next;
114            node.next.prev = node.prev;
115            node.next = null;
116            node.prev = null;
117            return node;
118        }
119
120        public Node removeLast() {
121            // remove the last node before the dummy tail (the least recently used one)
122            if (isEmpty()) {
123                return null; // list is empty, nothing to remove
124            }
125            return remove(tail.prev);
126        }
127
128        public boolean isEmpty() {
129            // check if the list is empty by seeing if the dummy head is directly connected to the dummy tail
130            return head.next == tail;
131        }
132    }
133}
134

1#include <unordered_map>
2using namespace std;
3
4// Node class representing a node in the doubly linked list
5class Node {
6public:
7    int key;        // Key of the node
8    int value;      // Value of the node
9    int freq;       // Frequency of accesses
10    Node* prev;     // Pointer to the previous node in the list
11    Node* next;     // Pointer to the next node in the list
12
13    // Constructor initializes a node with a key and a value
14    Node(int key, int value) : key(key), value(value), freq(1), prev(nullptr), next(nullptr) {}
15};
16
17// DoublyLinkedList class representing a doubly linked list
18class DoublyLinkedList {
19public:
20    Node* head;     // Pointer to the dummy head node
21    Node* tail;     // Pointer to the dummy tail node
22
23    // Constructor initializes the dummy head and tail and links them
24    DoublyLinkedList() {
25        head = new Node(-1, -1);
26        tail = new Node(-1, -1);
27        head->next = tail;
28        tail->prev = head;
29    }
30  
31    // Adds a node right after the head of the list
32    void add_first(Node* node) {
33        node->prev = head;
34        node->next = head->next;
35        head->next->prev = node;
36        head->next = node;
37    }
38  
39    // Removes the given node from the list and returns it
40    Node* remove(Node* node) {
41        node->next->prev = node->prev;
42        node->prev->next = node->next;
43        node->next = nullptr;
44        node->prev = nullptr;
45        return node;
46    }
47  
48    // Removes the last node before the tail and returns it
49    Node* remove_last() {
50        return remove(tail->prev);
51    }
52  
53    // Checks if the list is empty, i.e., only contains dummy head and tail
54    bool is_empty() {
55        return head->next == tail;
56    }
57};
58
59// LFUCache class representing the Least Frequently Used (LFU) Cache
60class LFUCache {
61public:
62    LFUCache(int capacity) : capacity(capacity), min_freq(0) {}
63  
64    int get(int key) {
65        if (capacity == 0 || key_to_node_map.find(key) == key_to_node_map.end()) {
66            return -1;
67        }
68        Node* node = key_to_node_map[key];
69        increase_frequency(node);
70        return node->value;
71    }
72  
73    void put(int key, int value) {
74        if (capacity == 0) return;
75      
76        if (key_to_node_map.find(key) != key_to_node_map.end()) {
77            Node* node = key_to_node_map[key];
78            node->value = value;
79            increase_frequency(node);
80        } else {
81            if (key_to_node_map.size() == capacity) {
82                DoublyLinkedList* list = freq_to_list_map[min_freq];
83                Node* removed_node = list->remove_last();
84                key_to_node_map.erase(removed_node->key);
85            }
86            Node* new_node = new Node(key, value);
87            add_node(new_node);
88            key_to_node_map[key] = new_node;
89            min_freq = 1;
90        }
91    }
92
93private:
94    int capacity;                                            // Capacity of the cache
95    int min_freq;                                            // Minimum frequency of nodes in the cache
96    unordered_map<int, Node*> key_to_node_map;               // Maps keys to their corresponding nodes
97    unordered_map<int, DoublyLinkedList*> freq_to_list_map;  // Maps frequencies to lists of nodes with that frequency
98
99    // Increases the frequency of a node
100    void increase_frequency(Node* node) {
101        int freq = node->freq;
102        DoublyLinkedList* list = freq_to_list_map[freq];
103        list->remove(node);
104        if (list->is_empty()) {
105            freq_to_list_map.erase(freq);
106            if (freq == min_freq) min_freq++;
107        }
108        node->freq++;
109        add_node(node);
110    }
111
112    // Adds a node to the list corresponding to its frequency
113    void add_node(Node* node) {
114        int freq = node->freq;
115        if (freq_to_list_map.find(freq) == freq_to_list_map.end()) {
116            freq_to_list_map[freq] = new DoublyLinkedList();
117        }
118        DoublyLinkedList* list = freq_to_list_map[freq];
119        list->add_first(node);
120    }
121};
122
123// Usage:
124// LFUCache* cache = new LFUCache(capacity);
125// int value = cache->get(key);
126// cache->put(key, value);
127

1// Representation of a node in the doubly linked list
2class Node {
3    public key: number;
4    public value: number;
5    public freq: number;
6    public prev: Node | null;
7    public next: Node | null;
8
9    constructor(key: number, value: number) {
10        this.key = key;
11        this.value = value;
12        this.freq = 1; // Initial frequency is set to 1
13        this.prev = null;
14        this.next = null;
15    }
16}
17
18// Representation of a doubly linked list
19class DoublyLinkedList {
20    public head: Node;
21    public tail: Node;
22
23    constructor() {
24        this.head = new Node(-1, -1); // Dummy head
25        this.tail = new Node(-1, -1); // Dummy tail
26        this.head.next = this.tail;
27        this.tail.prev = this.head;
28    }
29
30    // Adds a node right after the list's head
31    addFirst(node: Node): void {
32        node.prev = this.head;
33        node.next = this.head.next;
34        this.head.next!.prev = node;
35        this.head.next = node;
36    }
37
38    // Removes a node from the list
39    remove(node: Node): Node {
40        node.prev!.next = node.next;
41        node.next!.prev = node.prev;
42        return node;
43    }
44
45    // Removes and returns the last node before the list's tail
46    removeLast(): Node {
47        const nodeToRemove = this.tail.prev!;
48        return this.remove(nodeToRemove);
49    }
50
51    // Checks if the list is empty (only contains dummy head and tail)
52    isEmpty(): boolean {
53        return this.head.next === this.tail;
54    }
55}
56
57// Representation of the Least Frequently Used (LFU) Cache
58let capacity: number; // Capacity of the cache
59let minFreq: number; // Minimum frequency of nodes in the cache
60let keyToNodeMap = new Map<number, Node>(); // Maps keys to their corresponding nodes
61let freqToListMap = new Map<number, DoublyLinkedList>(); // Maps frequencies to lists of nodes with that frequency
62
63// Increases the frequency of a node, moving it to the appropriate frequency list
64function increaseFrequency(node: Node): void {
65    let freq = node.freq;
66    let list = freqToListMap.get(freq)!;
67    list.remove(node);
68    if (list.isEmpty()) {
69        freqToListMap.delete(freq);
70        if (freq === minFreq) {
71            minFreq++;
72        }
73    }
74    node.freq++;
75    addNode(node);
76}
77
78// Adds a node to the list corresponding to its frequency
79function addNode(node: Node): void {
80    let freq = node.freq;
81    if (!freqToListMap.has(freq)) {
82        freqToListMap.set(freq, new DoublyLinkedList());
83    }
84    let list = freqToListMap.get(freq)!;
85    list.addFirst(node);
86}
87
88// Creates a new LFU Cache with a given capacity
89function createCache(newCapacity: number): void {
90    capacity = newCapacity;
91    minFreq = 0;
92    keyToNodeMap.clear();
93    freqToListMap.clear();
94}
95
96// Retrieves the value for a key from the cache, or -1 if key is not present
97function get(key: number): number {
98    if (capacity === 0 || !keyToNodeMap.has(key)) {
99        return -1;
100    }
101
102    let node = keyToNodeMap.get(key)!;
103    increaseFrequency(node);
104    return node.value;
105}
106
107// Inserts a key-value pair into the cache, or updates the value if the key already exists
108function put(key: number, value: number): void {
109    if (capacity === 0) return;
110
111    if (keyToNodeMap.has(key)) {
112        let node = keyToNodeMap.get(key)!;
113        node.value = value;
114        increaseFrequency(node);
115    } else {
116        if (keyToNodeMap.size >= capacity) {
117            let list = freqToListMap.get(minFreq)!;
118            let removedNode = list.removeLast();
119            keyToNodeMap.delete(removedNode.key);
120        }
121        let newNode = new Node(key, value);
122        addNode(newNode);
123        keyToNodeMap.set(key, newNode);
124        minFreq = 1;
125    }
126}
127

Time and Space Complexity

Time Complexity

get() method:

The time complexity of the get method is O(1).
Accessing the node from the hashmap takes constant time, and the incr_freq method is designed to execute in constant time by performing a fixed number of pointer reference changes.

put() method:

The time complexity of the put method is O(1) for most of the operations which include checking the length of the hashmap, accessing the node from the hashmap, updating the value, and incrementing the frequency through incr_freq.
However, when the cache is full, we need to remove the least frequently used item, which again is done in constant time because the DoublyLinkedList allows us to remove the last element efficiently and the hashmap provides instant access to any node.

incr_freq() method:

The incr_freq method has a time complexity of O(1) because it involves removing a node from one frequency list and adding it to another, which entails only changing a few pointers around.
If the removed frequency list is empty, it pops the list from the frequency map in constant time and potentially increases the minimum frequency.

add_node() method:

The add_node method's time complexity is also O(1) as it simply adds the node to the front of the frequency list, which again involves a few pointer changes.

Space Complexity

LFUCache class:

The space complexity of the LFUCache class is O(capacity), where capacity is the maximum number of elements that the cache can hold.
Since each key and each frequency list takes up space, and the list grows as more unique items with distinct frequencies are added, the space complexity scales with the number of items, which is limited by capacity.
The use of two hashmaps (map and freq_map) ensures that the space used stays within a limit that is proportional to capacity.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What data structure does Breadth-first search typically uses to store intermediate states?

Stack

Queue

Tree

Linked List

I don't know