# 460. LFU Cache!

{% hint style="info" %}
LinkedHashSet, keyToValue, keyToFrequency, frequencyToKeys;
{% endhint %}

```java
class LFUCache {
    // to get value in O(1);
    private HashMap<Integer, Integer> keyToValues;
    // to update frequency in O(1);
    private HashMap<Integer, Integer> keyToFreqs;
    // to find least frequency in O(1);
    // because 1.one freq may maps to many keys
    // 2.for same reqs, get the key that is least recently used in O(1);
    // 3.need to delete the key and insert the key to (freq+1) in O(1);
    private HashMap<Integer, LinkedHashSet<Integer>> freqToKeys;
    
    private int minFreq;
    private int capacity;
    public LFUCache(int capacity) {
        keyToValues = new HashMap<>();
        keyToFreqs = new HashMap<>();
        freqToKeys = new HashMap<>();
        this.capacity = capacity;
    }
    
    private void updateFreq(int key, int freq){
        //update keyToFreqs
        keyToFreqs.put(key, freq);
        //update freqToKeys
        //previous freq is either not exist or freq-1;
        if(!freqToKeys.containsKey(freq)) 
            freqToKeys.put(freq, new LinkedHashSet<>());
        freqToKeys.get(freq).add(key);
        
        if(freq!=1) freqToKeys.get(freq-1).remove(key);
        
        //update minFreq;
        if(freq==1) minFreq=1;
        else if(freq-1==minFreq && freqToKeys.get(freq-1).size()==0) minFreq=freq;    
    }
    
    public int get(int key) {
       if(keyToValues.containsKey(key)){
           int freq = keyToFreqs.get(key)+1;
           updateFreq(key, freq);
           return keyToValues.get(key);
       }else{
           return -1;
       } 
    }
    
    public void put(int key, int value) {
        // corner case;
        if(capacity<=0) return;
        if(keyToValues.containsKey(key)){
            keyToValues.put(key, value);
            //update the frequency;
            updateFreq(key, keyToFreqs.get(key)+1);
        }else{
            if(keyToValues.size()==capacity){
                LinkedHashSet<Integer> keys = freqToKeys.get(minFreq);
                //first in first out
                int keyToDelete = keys.iterator().next();
                
                // delete the least freq element;
                keys.remove(keyToDelete);
                keyToFreqs.remove(keyToDelete);
                keyToValues.remove(keyToDelete);
            }
            
            keyToValues.put(key, value);
            updateFreq(key, 1);
        }
    }
}

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