## Algorithm

Problem Name: 460. LFU Cache

Design and implement a data structure for a Least Frequently Used (LFU) 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(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(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:

• `0 <= capacity <= 104`
• `0 <= key <= 105`
• `0 <= value <= 109`
• At most `2 * 105` calls will be made to `get` and `put`.

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(3);       // returns 3.
cache.put(4, 4);    // evicts key 1.
cache.get(3);       // returns 3
cache.get(4);       // returns 4
*/

typedef struct item_s {
int key;
int val;
int ref;
struct item_s *prev;
struct item_s *next;
} item_t;
​
typedef struct {
int sz;
item_t **data;
item_t *buff;
} LFUCache;
​
LFUCache* lFUCacheCreate(int capacity) {
LFUCache *p;
item_t *buff;
int i;

if (capacity  < = 0) return NULL;

p = malloc(sizeof(item_t));
//assert(p);
p->data = calloc(capacity, sizeof(item_t *));
//assert(p->data);
buff = calloc(capacity, sizeof(item_t));
//assert(buff);

if (capacity > 1) {
buff[0].next = &buff[1];
for (i = 1; i  <  capacity - 1; i ++) {
buff[i].prev = &buff[i - 1];
buff[i].next = &buff[i + 1];
}
buff[capacity - 1].prev = &buff[capacity - 2];
}
​
p->sz = capacity;

return p;
}
​
void move2next(item_t *t, LFUCache *obj) {
item_t *a, *b;

a = t;
b = t->next;
while (b && b->ref  < = t->ref) {
a = b;
b = b->next;
}
if (a != t) {
t->next->prev = t->prev;
if (t->prev) t->prev->next = t->next;
a->next = t;
t->prev = a;
t->next = b;
if (b) b->prev = t;
}
}
item_t *lookup(LFUCache* obj, int key) {
item_t *t;

t = obj->data[key % obj->sz];
while (t && t->key != key) {
}

return t;
}
int lFUCacheGet(LFUCache* obj, int key) {
item_t *t, *n, *np;

t = obj ? lookup(obj, key) : NULL;
if (!t) {
return -1;
}

t->ref ++;

move2next(t, obj);

return t->val;
}
void lFUCachePut(LFUCache* obj, int key, int value) {
item_t *t, **pp;

if (!obj) return;

t = lookup(obj, key);

if (!t) {
t = obj->head; // least frequently used

// take it out of the cache
pp = &obj->data[t->key % obj->sz];
while (*pp && *pp != t) {
}
if (*pp) {
}

// put it back with new key
t->key = key;
t->ref = 1;
obj->data[key % obj->sz] = t;
} else {
t->ref ++;
}

t->val = value;

move2next(t, obj);
}
​
void lFUCacheFree(LFUCache* obj) {
if (!obj) return;
free(obj->buff);
free(obj->data);
free(obj);
}
​
``````
Copy The Code &

Input

cmd
["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

cmd
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]

### #2 Code Example with Java Programming

```Code - Java Programming```

``````
class LFUCache {

private final Map keyToNodeMap;
private final Map < Integer, Node[]> frequencyToNodeMap;
private final Map keyToFrequencyMap;
private int capacity;
private int currentCapacity;

public LFUCache(int capacity) {
this.capacity = capacity;
this.currentCapacity = 0;
this.keyToNodeMap = new HashMap < >();
this.frequencyToNodeMap = new TreeMap<>();
this.keyToFrequencyMap = new HashMap < >();
}

public int get(int key) {
if (!keyToNodeMap.containsKey(key)) {
return -1;
}
Node node = keyToNodeMap.get(key);
removeNode(node);
int currentFrequency = keyToFrequencyMap.get(key);
int newFrequency = currentFrequency + 1;
keyToFrequencyMap.put(key, newFrequency);
return node.val;
}

public void put(int key, int value) {
if (this.capacity == 0) {
return;
}
removeNodeIfCapacityReached(key);
Node node = getNode(key, value);
int newFrequency = keyToFrequencyMap.getOrDefault(key, 0) + 1;
keyToFrequencyMap.put(key, newFrequency);
keyToNodeMap.put(key, node);
if (newFrequency > 1) {
removeNode(node);
}
}

private void removeNodeIfCapacityReached(int key) {
if (!keyToNodeMap.containsKey(key) && this.currentCapacity == capacity) {
for (Integer freq : frequencyToNodeMap.keySet()) {
Node[] nodes = frequencyToNodeMap.get(freq);
if (nodes[1].prev.val == -1) {
continue;
}
Node toRemove = nodes[1].prev;
removeNode(toRemove);
keyToNodeMap.remove(toRemove.key);
keyToFrequencyMap.remove(toRemove.key);
this.currentCapacity--;
break;
}
}
}

private Node getNode(int key, int value) {
Node node;
if (keyToNodeMap.containsKey(key)) {
node = keyToNodeMap.get(key);
removeNode(node);
node.val = value;
} else {
this.currentCapacity++;
node = new Node(value, key);
}
return node;
}

if (!frequencyToNodeMap.containsKey(newFrequency)) {
Node head = new Node(-1, Integer.MIN_VALUE);
Node tail = new Node(-1, Integer.MAX_VALUE);
}
}

private void removeNode(Node node) {
Node prevNode = node.prev;
Node nextNode = node.next;
prevNode.next = nextNode;
nextNode.prev = prevNode;
}

private static class Node {
int val;
int key;
Node next;
Node prev;

public Node(int val, int key) {
this.val = val;
this.key = key;
}
}
}
``````
Copy The Code &

Input

cmd
["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

cmd
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const LFUCache = function(capacity) {
this.min = -1;
this.capacity = capacity;
this.keyToVal = {};
this.keyToCount = {};
this.countToLRUKeys = {};
};

LFUCache.prototype.get = function(key) {
if (!this.keyToVal.hasOwnProperty(key)) return -1;
let count = this.keyToCount[key];
let idx = this.countToLRUKeys[count].indexOf(key);
if (idx !== -1) this.countToLRUKeys[count].splice(idx, 1);
if (count === this.min && this.countToLRUKeys[count].length === 0) this.min++;
putCount(key, count + 1, this.keyToCount, this.countToLRUKeys);
return this.keyToVal[key];
};

LFUCache.prototype.put = function(key, value) {
if (this.capacity  < = 0) return;

if (this.keyToVal.hasOwnProperty(key)) {
this.keyToVal[key] = value; // update key's value
this.get(key); // update key's count
return;
}

if (Object.keys(this.keyToVal).length >= this.capacity) {
evict(
this.countToLRUKeys[this.min][0],
this.min,
this.keyToVal,
this.countToLRUKeys
); // evict LRU from this min count bucket
}

this.min = 1;
putCount(key, this.min, this.keyToCount, this.countToLRUKeys); // adding new key and count
this.keyToVal[key] = value; // adding new key and value
};
function evict(key, min, keyToVal, countToLRUKeys) {
let idx = countToLRUKeys[min].indexOf(key);
if (idx !== -1) countToLRUKeys[min].splice(idx, 1);
delete keyToVal[key];
}
function putCount(key, count, keyToCount, countToLRUKeys) {
keyToCount[key] = count;
if (countToLRUKeys.hasOwnProperty(count)) {
countToLRUKeys[count].push(key);
} else {
countToLRUKeys[count] = [key];
}
}
``````
Copy The Code &

Input

cmd
["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

cmd
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class Node:
def __init__(self, k, v, f):
self.key = k
self.val = v
self.freq = f
self.next = self.pre = None
class LFUCache:

def __init__(self, capacity):
self.max = capacity
self.cache = 0
self.freqLast = {}
self.Nodes = {}
self.head = self.tail = Node("#", "#", "#")

def changeFreq(self, key):
node, f = self.Nodes[key], self.Nodes[key].freq
if self.freqLast[f] == node:
if node.pre.freq == f:
self.freqLast[f] = node.pre
else:
self.freqLast.pop(f)
if f + 1 in self.freqLast:
node.pre.next = node.next
node.next.pre = node.pre
node.pre = self.freqLast[f + 1]
node.next = node.pre.next
elif f in self.freqLast:
node.pre.next = node.next
node.next.pre = node.pre
node.pre = self.freqLast[f]
node.next = node.pre.next
node.pre.next = node.next.pre = node
self.freqLast[f + 1] = node
node.freq += 1

def removeFirst(self):
node.pre.next = node.next
node.next.pre = node.pre
self.Nodes.pop(node.key)
if self.freqLast[f] == node:
self.freqLast.pop(f)
self.cache -= 1

def get(self, key):
if key in self.Nodes:
self.changeFreq(key)
return self.Nodes[key].val
return -1
def put(self, key, value):
if key in self.Nodes:
self.changeFreq(key)
self.Nodes[key].val = value
elif self.max:
if self.cache == self.max:
self.removeFirst()
self.cache += 1
new = Node(key, value, 1)
if 1 in self.freqLast:
new.pre = self.freqLast[1]
else:
new.next = new.pre.next
new.pre.next = new.next.pre = new
self.freqLast[1] = self.Nodes[key] = new
``````
Copy The Code &

Input

cmd
["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

cmd
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]

### #5 Code Example with C# Programming

```Code - C# Programming```

``````
using System.Collections.Generic;
using System.Linq;

namespace LeetCode
{
public class _0460_LFUCache
{

public _0460_LFUCache(int capacity)
{
this.capacity = capacity;
frequencyList = new SortedDictionary < int, LinkedList<int[]>>();
map = new Dictionary < int, LinkedListNode<int[]>>();
}

public int Get(int key)
{
if (!map.ContainsKey(key))
return -1;
else
{
Reorder(map[key]);
}

return map[key].Value[1];
}

public void Put(int key, int value)
{
if (capacity == 0) return;
if (map.ContainsKey(key))
map[key].Value[1] = value;
else
{
if (map.Count >= capacity)
{
int min = frequencyList.Keys.First();
map.Remove(frequencyList[min].Last.Value[0]);
frequencyList[min].RemoveLast();

if (frequencyList[min].Count == 0)
frequencyList.Remove(min);
}

}

Reorder(map[key]);
}

private void Reorder(LinkedListNode < int[]> node)
{
var freq = node.Value[2];

if (frequencyList.ContainsKey(freq))
{
frequencyList[freq].Remove(node);
if (frequencyList[freq].Count == 0)
frequencyList.Remove(freq);
}

freq++;
node.Value[2]++;

if (!frequencyList.ContainsKey(freq))
}
}

}
``````
Copy The Code &

Input

cmd
["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

cmd
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]