# LFU Cache **Difficulty:** HARD [External](https://leetcode.com/problems/lfu-cache) Canonical: https://scaleengineer.com/dsa/problems/lfu-cache **Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design) **Algorithms:** [LRU Cache](https://scaleengineer.com/algorithms/lru-cache) **Data structures:** Hash Table, Linked List, Doubly-Linked List **Companies:** [DoorDash](https://scaleengineer.com/companies/doordash), [KLA](https://scaleengineer.com/companies/kla), [PayPal](https://scaleengineer.com/companies/paypal), [ServiceNow](https://scaleengineer.com/companies/servicenow), [Siemens](https://scaleengineer.com/companies/siemens), [Visa](https://scaleengineer.com/companies/visa), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Coupang](https://scaleengineer.com/companies/coupang), [Salesforce](https://scaleengineer.com/companies/salesforce), [Citadel](https://scaleengineer.com/companies/citadel), [Rippling](https://scaleengineer.com/companies/rippling), [Zomato](https://scaleengineer.com/companies/zomato), [Gameskraft](https://scaleengineer.com/companies/gameskraft) --- ## Problem Design and implement a data structure for a [Least Frequently Used (LFU)](https://en.wikipedia.org/wiki/Least%5Ffrequently%5Fused) cache. Implement the `LFUCache` class: * `LFUCache(int capacity)` Initializes the object with the `capacity` of the data structure. * `int get(int key)` Gets the value of the `key` if the `key` exists in the cache. Otherwise, returns `-1`. * `void put(int key, int value)` Update the value of the `key` if present, or inserts the `key` if not already present. When the cache reaches its `capacity`, it should invalidate and remove the **least frequently used** key before inserting a new item. For this problem, when there is a **tie** (i.e., two or more keys with the same frequency), the **least recently used** `key` would be invalidated. To determine the least frequently used key, a **use counter** is maintained for each key in the cache. The key with the smallest **use counter** is the least frequently used key. When a key is first inserted into the cache, its **use counter** is set to `1` (due to the `put` operation). The **use counter** for a key in the cache is incremented either a `get` or `put` operation is called on it. The functions `get` and `put` must each run in `O(1)` average time complexity. **Example 1:** **Input** ["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]] **Output** [null, null, null, 1, null, -1, 3, null, -1, 3, 4] **Explanation** // cnt(x) = the use counter for key x // cache=[] will show the last used order for tiebreakers (leftmost element is most recent) LFUCache lfu = new LFUCache(2); lfu.put(1, 1); // cache=[1,_], cnt(1)=1 lfu.put(2, 2); // cache=[2,1], cnt(2)=1, cnt(1)=1 lfu.get(1); // return 1 // cache=[1,2], cnt(2)=1, cnt(1)=2 lfu.put(3, 3); // 2 is the LFU key because cnt(2)=1 is the smallest, invalidate 2.   // cache=[3,1], cnt(3)=1, cnt(1)=2 lfu.get(2); // return -1 (not found) lfu.get(3); // return 3 // cache=[3,1], cnt(3)=2, cnt(1)=2 lfu.put(4, 4); // Both 1 and 3 have the same cnt, but 1 is LRU, invalidate 1. // cache=[4,3], cnt(4)=1, cnt(3)=2 lfu.get(1); // return -1 (not found) lfu.get(3); // return 3 // cache=[3,4], cnt(4)=1, cnt(3)=3 lfu.get(4); // return 4 // cache=[4,3], cnt(4)=2, cnt(3)=3 **Constraints:** * `1 <= capacity <= 104` * `0 <= key <= 105` * `0 <= value <= 109` * At most `2 * 105` calls will be made to `get` and `put`. # Approaches ## Brute Force with Linear Scan This approach uses a single hash map for O(1) lookups. Each entry in the map stores not only the value but also metadata: its usage frequency and a timestamp for its last access. When an eviction is necessary, the entire cache is scanned to find the item with the lowest frequency. Any ties are broken by choosing the item that was least recently used (i.e., has the oldest timestamp). **Time:** `get`: O(1) `put`: O(C), where C is the cache capacity. The need to scan the entire cache for eviction makes this approach inefficient for large capacities. · **Space:** O(C), where C is the cache capacity, to store the key-value pairs and their metadata in the hash map. **Pros:** Relatively simple to conceptualize and implement.; The `get` operation is efficient with O(1) time complexity. **Cons:** The `put` operation has a time complexity of O(C) where C is the capacity, which fails to meet the problem's O(1) requirement.; Performance degrades significantly as the cache capacity increases. ### Explanation The implementation revolves around a `HashMap` and a global `timer`. The `CacheEntry` class is a simple container for the `value`, `frequency`, and `lastAccessTime`. **`get(key)` Operation:** This is straightforward. We look up the key in the map. If it exists, we update its frequency and timestamp, then return the value. This is an O(1) operation. **`put(key, value)` Operation:** If the key already exists, we update its value and metadata, similar to a `get` operation. If the key is new, we first check if the cache is full. If it is, the eviction process begins. We must perform a linear scan through all the entries in the hash map's values. During this scan, we keep track of the entry with the lowest frequency found so far, using the last access time as a tie-breaker. Once the victim entry is identified, it's removed. Finally, the new entry is inserted with a frequency of 1. This eviction scan makes the `put` operation O(C), where C is the capacity. ```java class LFUCache { class CacheEntry { int value; int frequency; int accessTime; CacheEntry(int value, int frequency, int accessTime) { this.value = value; this.frequency = frequency; this.accessTime = accessTime; } } private Map cache; private int capacity; private int timer; public LFUCache(int capacity) { this.cache = new HashMap<>(); this.capacity = capacity; this.timer = 0; } public int get(int key) { if (!cache.containsKey(key)) { return -1; } CacheEntry entry = cache.get(key); entry.frequency++; entry.accessTime = timer++; return entry.value; } public void put(int key, int value) { if (capacity == 0) { return; } if (cache.containsKey(key)) { CacheEntry entry = cache.get(key); entry.value = value; entry.frequency++; entry.accessTime = timer++; } else { if (cache.size() >= capacity) { int keyToEvict = -1; int minFreq = Integer.MAX_VALUE; int minTime = Integer.MAX_VALUE; for (Map.Entry mapEntry : cache.entrySet()) { CacheEntry current = mapEntry.getValue(); if (current.frequency < minFreq) { minFreq = current.frequency; minTime = current.accessTime; keyToEvict = mapEntry.getKey(); } else if (current.frequency == minFreq && current.accessTime < minTime) { minTime = current.accessTime; keyToEvict = mapEntry.getKey(); } } cache.remove(keyToEvict); } cache.put(key, new CacheEntry(value, 1, timer++)); } } } ``` ### Algorithm * Initialize a `HashMap` to store cache data, where `CacheEntry` holds the value, frequency, and a `lastAccessTime`. * Maintain a global `timer` variable, incremented on each operation to provide a sequential timestamp. * For `get(key)`: 1. Retrieve `CacheEntry` from the map. If it doesn't exist, return -1. 2. Increment the entry's frequency. 3. Update its `lastAccessTime` with the current `timer` value and increment the `timer`. 4. Return the value. * For `put(key, value)`: 1. If the key exists, update its value, increment its frequency, and update its `lastAccessTime`. 2. If the key does not exist: * Check if the cache is full (`map.size() == capacity`). * If full, iterate through all entries in the map to find the one with the minimum frequency. If there's a tie, choose the one with the minimum `lastAccessTime`. * Remove this LFU/LRU entry from the map. * Create a new `CacheEntry` with frequency 1 and the current timestamp, and insert it into the map. ## Using a Min-Heap (Priority Queue) This approach improves upon the linear scan by using a min-heap (implemented as a `PriorityQueue` in Java) to more efficiently find the LFU/LRU item for eviction. The heap is ordered by frequency, and then by access time as a tie-breaker. This reduces the time to find the eviction candidate from O(C) to O(log C). A key challenge is updating an item's priority in the heap, which is handled using a "lazy removal" strategy: instead of updating an item, we add a new version and mark the old one as stale, to be cleaned up during eviction. **Time:** `get`: O(log C) `put`: O(log C) Both operations involve adding to the heap. The eviction process in `put` might poll multiple stale entries, but this is amortized to O(log C). · **Space:** O(C + M), where C is the capacity and M is the number of `get`/`put` operations that cause updates. The heap can store stale entries, so its size can exceed the capacity. **Pros:** Much more efficient than the linear scan approach, with logarithmic time complexity.; Conceptually builds upon the brute-force idea by optimizing the search for the eviction candidate. **Cons:** Does not meet the strict O(1) time complexity requirement.; Space complexity can be higher than the capacity due to stale entries accumulating in the heap.; The logic for handling stale entries adds complexity to the implementation. ### Explanation This method combines a hash map for fast lookups with a min-heap for efficient eviction selection. * **Data Structures**: A `HashMap` provides O(1) access to entries. A `PriorityQueue` keeps the entries sorted by `(frequency, accessTime)`, so the LFU/LRU element is always at the top. * **Lazy Removal**: A standard heap doesn't support efficient updates of arbitrary elements. To work around this, when an entry's frequency is updated (via `get` or `put`), we don't remove the old version from the heap. Instead, we add the new, updated version to the heap and update the hash map to point to this new version. The old entry in the heap becomes "stale". * **Eviction**: When we need to evict, we poll the top element from the heap. We must verify if it's stale by comparing it with the entry stored in our hash map. If `map.get(polledEntry.key)` is not the same as `polledEntry`, it's stale, and we discard it and poll again. This continues until we find a valid, non-stale entry to evict. ```java class LFUCache { class CacheEntry implements Comparable { int key, value, frequency, accessTime; CacheEntry(int key, int value, int frequency, int accessTime) { this.key = key; this.value = value; this.frequency = frequency; this.accessTime = accessTime; } @Override public int compareTo(CacheEntry other) { if (this.frequency != other.frequency) { return this.frequency - other.frequency; } return this.accessTime - other.accessTime; } } private Map cache; private PriorityQueue minHeap; private int capacity; private int timer; public LFUCache(int capacity) { this.cache = new HashMap<>(); this.minHeap = new PriorityQueue<>(); this.capacity = capacity; this.timer = 0; } public int get(int key) { if (!cache.containsKey(key)) { return -1; } CacheEntry entry = cache.get(key); CacheEntry newEntry = new CacheEntry(key, entry.value, entry.frequency + 1, timer++); cache.put(key, newEntry); minHeap.offer(newEntry); return entry.value; } public void put(int key, int value) { if (capacity == 0) { return; } if (cache.containsKey(key)) { CacheEntry entry = cache.get(key); CacheEntry newEntry = new CacheEntry(key, value, entry.frequency + 1, timer++); cache.put(key, newEntry); minHeap.offer(newEntry); } else { if (cache.size() >= capacity) { while (!minHeap.isEmpty()) { CacheEntry toEvict = minHeap.poll(); // Check if it's a stale entry if (cache.containsKey(toEvict.key) && cache.get(toEvict.key) == toEvict) { cache.remove(toEvict.key); break; } } } CacheEntry newEntry = new CacheEntry(key, value, 1, timer++); cache.put(key, newEntry); minHeap.offer(newEntry); } } } ``` ### Algorithm * Use a `HashMap` for O(1) lookups. `CacheEntry` stores key, value, frequency, and access time. * Use a `PriorityQueue` (min-heap) ordered first by frequency, then by access time. * Maintain a global `timer`. * For `get(key)` or `put(key, value)` on an existing key: 1. Retrieve the old `CacheEntry` from the map. 2. Create a *new* `CacheEntry` with the updated frequency and timestamp. 3. Update the map to point to the new entry. 4. Add the new entry to the heap. The old entry in the heap is now considered "stale". * For `put(key, value)` on a new key: 1. If the cache is full, perform eviction. 2. **Eviction**: Repeatedly poll from the heap. If the polled entry is stale (i.e., its data doesn't match the entry in the map for that key), discard it and poll again. Continue until a valid entry is polled. 3. Remove the valid evicted key from the map. 4. Create a new `CacheEntry` and add it to both the map and the heap. ## O(1) Solution with Two HashMaps and Doubly Linked Lists This is the optimal O(1) solution. It achieves constant time complexity for both `get` and `put` by using a sophisticated combination of data structures. A primary hash map provides O(1) lookups. A second hash map groups cache items by their frequency. Each frequency group is a doubly linked list (DLL) that maintains the least-recently-used (LRU) order for that specific frequency. This allows for O(1) eviction of the LFU item, and O(1) tie-breaking using the LRU policy. **Time:** `get`: O(1) `put`: O(1) All constituent operations (hash map lookups/insertions, DLL additions/removals) are constant time. · **Space:** O(C), where C is the cache capacity. The `cache` map, `freqMap`, and all nodes within the linked lists will store a total of C items. **Pros:** Achieves the optimal O(1) average time complexity for both `get` and `put` operations.; Space complexity is strictly bounded by the cache capacity O(C). **Cons:** Significantly more complex to implement correctly compared to other approaches.; Requires careful management of pointers in the doubly linked list and state across multiple data structures. ### Explanation This approach masterfully combines hash maps and doubly linked lists to meet the O(1) time complexity requirement. * **`cache` (`HashMap`)**: Maps a key to its `Node`. The `Node` contains the key, value, frequency, and pointers (`prev`, `next`) for the DLL. * **`freqMap` (`HashMap`)**: Maps a frequency count to a `DoublyLinkedList` instance. This DLL contains all nodes with that frequency. * **`DoublyLinkedList`**: A custom class that manages a list of nodes. It has methods to add a node to the head (`addNode`) and remove a node from any position (`removeNode`), both in O(1). It also tracks its head and tail. * **`minFrequency`**: An integer that always points to the lowest frequency currently in the cache. This is the key to O(1) eviction, as we can directly access the correct DLL in `freqMap` using `freqMap.get(minFrequency)`. **Operation Flow:** When a node is accessed (`get` or `put`), its frequency must be incremented. This means it must move from the DLL of its current frequency (`f`) to the DLL of the next frequency (`f+1`). 1. It's removed from the `f` DLL. 2. If the `f` DLL becomes empty and `f` was the `minFrequency`, we increment `minFrequency`. 3. The node's frequency is updated, and it's added to the head of the `f+1` DLL (which is created if it doesn't exist). When a new node is inserted, it always has a frequency of 1. It's added to the head of the DLL for frequency 1, and `minFrequency` is reset to 1. ```java class LFUCache { class Node { int key, value, freq; Node prev, next; Node(int key, int value) { this.key = key; this.value = value; this.freq = 1; } } class DoublyLinkedList { Node head, tail; int size; DoublyLinkedList() { head = new Node(0, 0); // Dummy head tail = new Node(0, 0); // Dummy tail head.next = tail; tail.prev = head; size = 0; } void addNode(Node node) { // Add to head node.next = head.next; head.next.prev = node; head.next = node; node.prev = head; size++; } void removeNode(Node node) { node.prev.next = node.next; node.next.prev = node.prev; size--; } Node removeTail() { if (size == 0) return null; Node nodeToRemove = tail.prev; removeNode(nodeToRemove); return nodeToRemove; } } private final int capacity; private int minFrequency; private Map cache; private Map freqMap; public LFUCache(int capacity) { this.capacity = capacity; this.minFrequency = 0; this.cache = new HashMap<>(); this.freqMap = new HashMap<>(); } private void updateNode(Node node) { DoublyLinkedList oldList = freqMap.get(node.freq); oldList.removeNode(node); if (node.freq == minFrequency && oldList.size == 0) { minFrequency++; } node.freq++; DoublyLinkedList newList = freqMap.getOrDefault(node.freq, new DoublyLinkedList()); newList.addNode(node); freqMap.put(node.freq, newList); } public int get(int key) { if (!cache.containsKey(key)) { return -1; } Node node = cache.get(key); updateNode(node); return node.value; } public void put(int key, int value) { if (capacity == 0) return; if (cache.containsKey(key)) { Node node = cache.get(key); node.value = value; updateNode(node); } else { if (cache.size() >= capacity) { DoublyLinkedList lfuList = freqMap.get(minFrequency); Node nodeToEvict = lfuList.removeTail(); cache.remove(nodeToEvict.key); } Node newNode = new Node(key, value); cache.put(key, newNode); minFrequency = 1; DoublyLinkedList newList = freqMap.getOrDefault(1, new DoublyLinkedList()); newList.addNode(newNode); freqMap.put(1, newList); } } } ``` ### Algorithm * Use a `cache` map (`HashMap`) for O(1) key-to-node lookups. * Use a `freqMap` (`HashMap`) to group nodes by frequency. Each frequency maps to a DLL of nodes with that frequency. * The DLLs maintain LRU order: new/updated nodes are added to the head, and eviction candidates are removed from the tail. * Maintain a `minFrequency` integer to track the lowest frequency in the cache, allowing for O(1) identification of the LFU list. * **`updateNode(node)`**: A helper function to promote a node to a higher frequency. It removes the node from its current frequency's DLL and adds it to the head of the next frequency's DLL. It also updates `minFrequency` if a frequency list becomes empty. * **`get(key)`**: Find the node in `cache`, call `updateNode` on it, and return its value. * **`put(key, value)`**: * If key exists, update its value and call `updateNode`. * If new: * If at capacity, evict: get the DLL for `minFrequency`, remove its tail node, and remove that node's key from the `cache` map. * Create a new node, add it to `cache`, add it to the DLL for frequency 1, and reset `minFrequency` to 1. # Solutions ### Java ```java public class LFU_Cache { public class LFUCache { // Save the key, value HashMap < Integer , Integer > vals ; // Save the key to the value of the number of visits HashMap < Integer , Integer > counts ; // 频率和一个里面所有key都是当前频率的list之间的映射 HashMap < Integer , LinkedHashSet < Integer >> lists ; int capacity ; // Initialize the frequency of data occurrences int min = - 1 ; public LFUCache ( int cap ) { capacity = cap ; vals = new HashMap <>(); counts = new HashMap <>(); lists = new HashMap <>(); } public int get ( int key ) { if (! vals . containsKey ( key )) return - 1 ; int count = counts . get ( key ); counts . put ( key , count + 1 ); lists . get ( count ). remove ( key ); // Determine whether min should add 1 if ( count == min && lists . get ( count ). size () == 0 ) { min ++; } if (! lists . containsKey ( count + 1 )) { lists . put ( count + 1 , new LinkedHashSet <>()); } lists . get ( count + 1 ). add ( key ); return vals . get ( key ); } public void put ( int key , int value ) { if ( capacity <= 0 ) return ; if ( vals . containsKey ( key )) { vals . put ( key , value ); get ( key ); return ; } if ( vals . size () >= capacity ) { int minFreKey = lists . get ( min ). iterator (). next (); lists . get ( min ). remove ( minFreKey ); vals . remove ( minFreKey ); counts . remove ( minFreKey ); } vals . put ( key , value ); counts . put ( key , 1 ); min = 1 ; if (! lists . containsKey ( 1 )) { lists . put ( 1 , new LinkedHashSet <>()); } lists . get ( 1 ). add ( key ); } } } ############ class LFUCache { private final Map < Integer , Node > map ; private final Map < Integer , DoublyLinkedList > freqMap ; private final int capacity ; private int minFreq ; public LFUCache ( int capacity ) { this . capacity = capacity ; map = new HashMap <>( capacity , 1 ); freqMap = new HashMap <>(); } public int get ( int key ) { if ( capacity == 0 ) { return - 1 ; } if (! map . containsKey ( key )) { return - 1 ; } Node node = map . get ( key ); incrFreq ( node ); return node . value ; } public void put ( int key , int value ) { if ( capacity == 0 ) { return ; } if ( map . containsKey ( key )) { Node node = map . get ( key ); node . value = value ; incrFreq ( node ); return ; } if ( map . size () == capacity ) { DoublyLinkedList list = freqMap . get ( minFreq ); map . remove ( list . removeLast (). key ); } Node node = new Node ( key , value ); addNode ( node ); map . put ( key , node ); minFreq = 1 ; } private void incrFreq ( Node node ) { int freq = node . freq ; DoublyLinkedList list = freqMap . get ( freq ); list . remove ( node ); if ( list . isEmpty ()) { freqMap . remove ( freq ); if ( freq == minFreq ) { minFreq ++; } } node . freq ++; addNode ( node ); } private void addNode ( Node node ) { int freq = node . freq ; DoublyLinkedList list = freqMap . getOrDefault ( freq , new DoublyLinkedList ()); list . addFirst ( node ); freqMap . put ( freq , list ); } private static class Node { int key ; int value ; int freq ; Node prev ; Node next ; Node ( int key , int value ) { this . key = key ; this . value = value ; this . freq = 1 ; } } private static class DoublyLinkedList { private final Node head ; private final Node tail ; public DoublyLinkedList () { head = new Node (- 1 , - 1 ); tail = new Node (- 1 , - 1 ); head . next = tail ; tail . prev = head ; } public void addFirst ( Node node ) { node . prev = head ; node . next = head . next ; head . next . prev = node ; head . next = node ; } public Node remove ( Node node ) { node . next . prev = node . prev ; node . prev . next = node . next ; node . next = null ; node . prev = null ; return node ; } public Node removeLast () { return remove ( tail . prev ); } public boolean isEmpty () { return head . next == tail ; } } } ``` ### Python ```python from collections import defaultdict class LFUCache : def __init__ ( self , capacity : int ): self . capacity = capacity self . key_to_value = {} self . key_to_freq = defaultdict ( int ) self . freq_to_keys = defaultdict ( OrderedDict ) self . min_freq = 0 def get ( self , key : int ) -> int : if key not in self . key_to_value : return - 1 # Update the frequency self . _update_frequency ( key ) return self . key_to_value [ key ] def put ( self , key : int , value : int ) -> None : if self . capacity == 0 : return if key in self . key_to_value : # Update the value and frequency self . key_to_value [ key ] = value self . _update_frequency ( key ) else : if len ( self . key_to_value ) >= self . capacity : # Evict the least frequently used key self . _evict () # Add the new key-value pair self . key_to_value [ key ] = value self . key_to_freq [ key ] = 1 self . freq_to_keys [ 1 ][ key ] = None self . min_freq = 1 def _update_frequency ( self , key : int ) -> None : freq = self . key_to_freq [ key ] del self . freq_to_keys [ freq ][ key ] if not self . freq_to_keys [ freq ]: # If there are no keys with the previous frequency, update min_freq if self . min_freq == freq : self . min_freq += 1 del self . freq_to_keys [ freq ] freq += 1 self . key_to_freq [ key ] = freq self . freq_to_keys [ freq ][ key ] = None def _evict ( self ) -> None : keys = self . freq_to_keys [ self . min_freq ] evict_key , _ = keys . popitem ( last = False ) del self . key_to_value [ evict_key ] del self . key_to_freq [ evict_key ] # Your LFUCache object will be instantiated and called as such: # obj = LFUCache(capacity) # param_1 = obj.get(key) # obj.put(key,value) ########## class Node : def __init__ ( self , key : int , value : int ) -> None : self . key = key self . value = value self . freq = 1 self . prev = None self . next = None class DoublyLinkedList : def __init__ ( self ) -> None : self . head = Node ( - 1 , - 1 ) self . tail = Node ( - 1 , - 1 ) self . head . next = self . tail self . tail . prev = self . head def add_first ( self , node : Node ) -> None : node . prev = self . head node . next = self . head . next self . head . next . prev = node self . head . next = node def remove ( self , node : Node ) -> Node : node . next . prev = node . prev node . prev . next = node . next node . next , node . prev = None , None return node def remove_last ( self ) -> Node : return self . remove ( self . tail . prev ) def is_empty ( self ) -> bool : return self . head . next == self . tail class LFUCache : def __init__ ( self , capacity : int ): self . capacity = capacity self . min_freq = 0 self . map = defaultdict ( Node ) self . freq_map = defaultdict ( DoublyLinkedList ) def get ( self , key : int ) -> int : if self . capacity == 0 or key not in self . map : return - 1 node = self . map [ key ] self . incr_freq ( node ) return node . value def put ( self , key : int , value : int ) -> None : if self . capacity == 0 : return if key in self . map : node = self . map [ key ] node . value = value self . incr_freq ( node ) return if len ( self . map ) == self . capacity : ls = self . freq_map [ self . min_freq ] node = ls . remove_last () self . map . pop ( node . key ) node = Node ( key , value ) self . add_node ( node ) self . map [ key ] = node self . min_freq = 1 def incr_freq ( self , node : Node ) -> None : freq = node . freq ls = self . freq_map [ freq ] ls . remove ( node ) if ls . is_empty (): self . freq_map . pop ( freq ) if freq == self . min_freq : self . min_freq += 1 node . freq += 1 self . add_node ( node ) def add_node ( self , node : Node ) -> None : freq = node . freq ls = self . freq_map [ freq ] ls . add_first ( node ) self . freq_map [ freq ] = ls # Your LFUCache object will be instantiated and called as such: # obj = LFUCache(capacity) # param_1 = obj.get(key) # obj.put(key,value) ``` ### CPP ```cpp class Node { public: int key ; int value ; int freq ; Node * prev ; Node * next ; Node ( int key , int value ) { this -> key = key ; this -> value = value ; this -> freq = 1 ; this -> prev = nullptr ; this -> next = nullptr ; } }; class DoublyLinkedList { public: Node * head ; Node * tail ; DoublyLinkedList () { this -> head = new Node ( - 1 , - 1 ); this -> tail = new Node ( - 1 , - 1 ); this -> head -> next = this -> tail ; this -> tail -> prev = this -> head ; } void addFirst ( Node * node ) { node -> prev = this -> head ; node -> next = this -> head -> next ; this -> head -> next -> prev = node ; this -> head -> next = node ; } Node * remove ( Node * node ) { node -> next -> prev = node -> prev ; node -> prev -> next = node -> next ; node -> next = nullptr ; node -> prev = nullptr ; return node ; } Node * removeLast () { return remove ( this -> tail -> prev ); } bool isEmpty () { return this -> head -> next == this -> tail ; } }; class LFUCache { public: LFUCache ( int capacity ) { this -> capacity = capacity ; this -> minFreq = 0 ; } int get ( int key ) { if ( capacity == 0 || map . find ( key ) == map . end ()) { return - 1 ; } Node * node = map [ key ]; incrFreq ( node ); return node -> value ; } void put ( int key , int value ) { if ( capacity == 0 ) { return ; } if ( map . find ( key ) != map . end ()) { Node * node = map [ key ]; node -> value = value ; incrFreq ( node ); return ; } if ( map . size () == capacity ) { DoublyLinkedList * list = freqMap [ minFreq ]; Node * node = list -> removeLast (); map . erase ( node -> key ); } Node * node = new Node ( key , value ); addNode ( node ); map [ key ] = node ; minFreq = 1 ; } private: int capacity ; int minFreq ; unordered_map < int , Node *> map ; unordered_map < int , DoublyLinkedList *> freqMap ; void incrFreq ( Node * node ) { int freq = node -> freq ; DoublyLinkedList * list = freqMap [ freq ]; list -> remove ( node ); if ( list -> isEmpty ()) { freqMap . erase ( freq ); if ( freq == minFreq ) { minFreq ++ ; } } node -> freq ++ ; addNode ( node ); } void addNode ( Node * node ) { int freq = node -> freq ; if ( freqMap . find ( freq ) == freqMap . end ()) { freqMap [ freq ] = new DoublyLinkedList (); } DoublyLinkedList * list = freqMap [ freq ]; list -> addFirst ( node ); freqMap [ freq ] = list ; } }; /** * Your LFUCache object will be instantiated and called as such: * LFUCache* obj = new LFUCache(capacity); * int param_1 = obj->get(key); * obj->put(key,value); */ ```