# 0460. LFU Cache

https://leetcode.com/problems/lfu-cache

## Description

Design and implement a data structure for a [Least Frequently Used (LFU)](https://en.wikipedia.org/wiki/Least_frequently_used) 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=[3,4], 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`.

&#x20;

## ac

```java
class LFUCache {
    int min, capacity;
    Map<Integer, Integer> keyToValue, keyToFreq;
    Map<Integer, LinkedHashSet<Integer>> freqBucket;

    public LFUCache(int capacity) {
        this.capacity = capacity;
        min = 0;
        keyToValue = new HashMap<>();
        keyToFreq  = new HashMap<>();
        freqBucket = new HashMap<>();
    }

    public int get(int key) {
        if (!keyToValue.containsKey(key)) return -1;
        addFreq(key);
        return keyToValue.get(key);
    }

    public void put(int key, int value) {
        if (capacity <= 0) return;

        if (keyToValue.containsKey(key)) { // update old value
            keyToValue.put(key, value);
            addFreq(key);
        } else { // add new value
            if (keyToValue.size() == capacity) removeLeastFreq();

            keyToValue.put(key, value);
            addFreq(key);
        }
    }

    private void addFreq(int key) {
        int freq = keyToFreq.getOrDefault(key, 0);

        keyToFreq.put(key, freq+1); // update freq
        if (freq == 0) min = 1; // you just add a new element, min must be 1

        if (freq > 0) removeKeyInFreqList(freq, key);
        if (!freqBucket.containsKey(freq+1)) freqBucket.put(freq+1, new LinkedHashSet<>());
        freqBucket.get(freq+1).add(key);
    }

    private void removeLeastFreq() {
        while (freqBucket.get(min).size() == 0) min++;

        int minKey = freqBucket.get(min).iterator().next();
        removeKeyInFreqList(min, minKey);
        keyToValue.remove(minKey);
        keyToFreq.remove(minKey);
    }

    private void removeKeyInFreqList(int freq, int key) {
        freqBucket.get(freq).remove(key);
        if(min == freq && freqBucket.get(freq).size() == 0) min++;
    }
}

/**
 * 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);
 */

/*
priority queue + hashmap, O(logn)

key:value
key:freq
key:freq-key

*/
```
