# Short Java O(1) solution using LinkedHashMap and HashMap with explaination

• The basic idea is to keep two maps:

1. keyToFreq: key -> frequency
2. freqToEntry: frequency -> (key,value) pairs with the same frequency, in LRU order (using LinkedHashMap)

Another important idea is to store and update the current minimum frequency. When it reaches the capacity, I remove the oldest entry from freqToEntry.get(min), and the next minimum frequency will be 1.

Here is my code:

``````public class LFUCache {

Map<Integer, Integer> keyToFreq;
int capacity;
int min;

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

public int get(int key) {
if(capacity==0 || !keyToFreq.containsKey(key)) {
return -1;
}else{
int freq = keyToFreq.get(key);
int value = freqToEntry.get(freq).get(key);
keyToFreq.put(key, freq+1);
freqToEntry.get(freq).remove(key);
if(freq==min && freqToEntry.get(freq).size()==0) min = min+1;
return value;
}
}

public void set(int key, int value) {
if(capacity==0) return;
if(keyToFreq.containsKey(key)){
int freq = keyToFreq.get(key);
keyToFreq.put(key, freq+1);
freqToEntry.get(freq).remove(key);
if(freq==min && freqToEntry.get(freq).size()==0) min = min+1;
}else{
if(keyToFreq.size()==capacity) removeOldest();
keyToFreq.put(key, 1);
min = 1;
}
}

private void removeOldest(){
int rmKey = freqToEntry.get(min).keySet().iterator().next();
keyToFreq.remove(rmKey);
freqToEntry.get(min).remove(rmKey);
}
}

``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.