public class LC460LFUCache {
node.prev.next = node.next;
node.next.prev = node.prev;
// always remove last node if last node exists
Map<Integer, Node> nodeMap;
Map<Integer, DoubleLinkedList> freqMap;
public LC460LFUCache(int capacity) {
this.capacity = capacity;
nodeMap = new HashMap<>();
freqMap = new HashMap<>();
public int get(int key) {
Node node = nodeMap.get(key);
if (node == null) return -1;
public void put(int key, int value) {
if (capacity == 0) return;
if (nodeMap.containsKey(key)) {
node = new Node(key, value);
if (nodeMap.size() == capacity) {
DoubleLinkedList lastList = freqMap.get(minFreq);
nodeMap.remove(lastList.removeLast().key);
DoubleLinkedList newList = freqMap.getOrDefault(node.freq, new DoubleLinkedList());
freqMap.put(node.freq, newList);
private void update(Node node) {
DoubleLinkedList oldList = freqMap.get(node.freq);
if (node.freq == minFreq && oldList.size == 0) minFreq++;
DoubleLinkedList newList = freqMap.getOrDefault(node.freq, new DoubleLinkedList());
freqMap.put(node.freq, newList);