# Java O(1), two hashMap, and one double linked list (147ms)

• Two Maps:
vals : key is the input key, value is the self-defined ListNode for double-linkedList
freqs : key is the freq number, value the self-defined FreqNode class representing the head and tail ListNode with this specific frequent.

global minFreq : to recode the current minimul frequency. In order to remove the oldest ListNode with least frequency in O(1) when it reaches the capacity

Example :
vals : L1(key, value, freq)
1 : L1(1,1,1)
2 : L2(2,2,3)
3 : L3(3,3,3)
4 : L4(4,4,1)
5 : L5(3,3,3)

freqs:
1 : L1 -> L4
3: L2 -> L3 -> L5

if we want to put(3,3)
The expected status of vals and maps would be :
vals : L1(key, value, freq)
1 : L1(1,1,1)
2 : L2(2,2,3)
3 : L3(3,3,4)
4 : L4(4,4,1)
5 : L5(3,3,3)

freqs:
1 : L1 -> L4
3: L2 -> L5
4 : L3

"remove" function is to remove L3 from freqs.get(3)
Two tricky part :
(1)when the ListNode you want to remove is from the minFreq and there is only one ListNode under this frequence --> your minFreq should increase by 1
(2) when the ListNode you want to remove is the only one under certain frequency --> you need to remove the entry with this frequnecy in freqs Map

"Insert" function : is to insert L3 to a new entry with old frequency + 1

``````class LFUCache {
private Map<Integer, ListNode> vals; //<key, ListNode>
private Map<Integer, FreqNode> freqs; //<freq, freqNode>
private final int capacity;
private int minFreq = -1;

public LFUCache(int capacity) {
this.capacity = capacity;
vals = new HashMap<>();
freqs = new HashMap<>();
}

public int get(int key) {
//System.out.println("get " + key);
ListNode curNode = vals.get(key);
if (curNode == null) {
return -1;
}

FreqNode freqNode = freqs.get(curNode.freq);
remove(curNode, freqNode);

FreqNode nextFreqNode = freqs.get(curNode.freq + 1);
insert(curNode, nextFreqNode);
return curNode.val;

}

public void put(int key, int value) {
//System.out.println("put " + key + " " + value);
if (capacity <= 0) {
return;
}

ListNode curNode = vals.get(key);
if (curNode != null) {
FreqNode freqNode = freqs.get(curNode.freq);

remove(curNode, freqNode);

FreqNode nextFreqNode = freqs.get(curNode.freq + 1);
insert(curNode, nextFreqNode);
curNode.val = value;
return;
}

if (vals.size() == capacity) {
//remove the tail in the least frequent

FreqNode minFreqNode = freqs.get(minFreq);
ListNode tail = minFreqNode.tail;
remove(minFreqNode.tail, minFreqNode);
vals.remove(tail.key);
}

minFreq = 1;
curNode = new ListNode(key, value, 0);
FreqNode nextFreqNode = freqs.get(1);
insert(curNode, nextFreqNode);
vals.put(key, curNode);

}

private void remove(ListNode curNode, FreqNode freqNode) {
if (curNode.prev != null) {
curNode.prev.next = curNode.next;
}
if (curNode.next != null) {
curNode.next.prev = curNode.prev;
}
}
if (freqNode.tail == curNode) {
freqNode.tail = curNode.prev;
}

curNode.prev = null;
curNode.next = null;
//minFreq should plus one, when you remove  the only ListNode in minimul frequency
if (curNode.freq == minFreq && freqNode.head == null) {
minFreq++;
}
//remove the entry in freqs Map when you remove the only freqNode in this frequency
freqs.remove(curNode.freq);
}

}

private void insert(ListNode curNode, FreqNode nextFreqNode) {
if (nextFreqNode == null) {
nextFreqNode = new FreqNode();
nextFreqNode.tail = curNode;
freqs.put(curNode.freq + 1, nextFreqNode);
} else {
}

curNode.freq = curNode.freq + 1;
}

}

class ListNode {
int key;
int val;
int freq;
ListNode prev;
ListNode next;
public ListNode(int key, int val, int freq) {
this.key = key;
this.val = val;
this.freq = freq;
}
}

//The ListNode of the head and tail to make remove in operation O(1) when reach capacity
class FreqNode {