# Concise Java solution by using only two HashMaps. Simple Double linked list structure, easy to understand and beat 95%.

• ``````class CacheNode {
int key, val, count;
CacheNode pre, next;

public CacheNode(int key, int val) {
this.key = key;
this.val = val;
this.count = 1;
}

}

public class LFUCache {
/**
* Store node position in doubly linked list <key, Node>.
*/
private Map<Integer, CacheNode> positionNodes = new HashMap<>();

/**
* Store access count and most recently used node among all of the same access count nodes
* <access_count, most_recently_node>.
*/
private Map<Integer, CacheNode> countMap = new HashMap<>();
private int capacity;
/**
* Tail pointer, avoid null point checks.
*/
private CacheNode tail;

public LFUCache(int capacity) {
this.capacity = capacity;
tail = new CacheNode(-1, -1);
tail.count = -1;
}

public int get(int key) {
if (this.capacity == 0) {
return -1;
}
CacheNode n = positionNodes.get(key);
return n == null ? -1 : increaseCount(key);
}

/**
* Insert node b behind node a.
*
* @param a
* @param b
*/
private void insert(CacheNode a, CacheNode b) {

/**
* Don't have to update the same node.
*/
if (a == b) {
return;
}
CacheNode next = a.next;
a.next = b;
b.pre = a;
if (next != null) {
next.pre = b;
}
b.next = next;
}

public void put(int key, int value) {
if (this.capacity == 0) {
return;
}
CacheNode n = positionNodes.get(key);
CacheNode recentlyUsed = countMap.get(1);

if (n == null) {
/**
* Always remove tail.
*/
if (positionNodes.size() >= this.capacity) {
this.removeNode(tail.next);
}
recentlyUsed = countMap.get(1);
CacheNode newNode = new CacheNode(key, value);
/**
* New node will be the most recently used node among of all nodes with access time 1.
*/
this.insert(((recentlyUsed == null) ? tail : recentlyUsed), newNode);
countMap.put(1, newNode);
positionNodes.put(key, newNode);
} else {
n.val = value;
increaseCount(key);
}
}

/**
*
* @param key
* @return
*/
private int increaseCount(int key) {
CacheNode curNode = positionNodes.get(key);
CacheNode recentlyUsed = countMap.get(curNode.count + 1);
if (recentlyUsed == null) {
/**
* If the count+1 number not in map, which means it can insert right after most recently used
* node with the same count.
*/
recentlyUsed = countMap.get(curNode.count);
}

if (recentlyUsed == null || recentlyUsed == curNode) {
/**
* No need to move postion.
*/
this.updateFrequence(curNode);
curNode.count++;
countMap.put(curNode.count, curNode);
} else {
int count = curNode.count;
this.removeNode(curNode);
CacheNode newNode = new CacheNode(key, curNode.val);
newNode.count = count + 1;

this.insert(recentlyUsed, newNode);
countMap.put(count + 1, newNode);
positionNodes.put(key, newNode);
}
return curNode.val;
}

/**
* When removing a record from countMap, always try to find if other node with the same count can
* promoted to most recently used node. Otherwise delete the record only.
*
* @param node
*/
private void updateFrequence(CacheNode node) {
if (countMap.get(node.count) == node) {
if (node.pre.count == node.count) {
countMap.put(node.count, node.pre);
} else {
countMap.remove(node.count);
}
}
}

/**
* Remove an existing node from the linked list.
*
* @param node to delete.
*/
private void removeNode(CacheNode node) {
this.updateFrequence(node);
CacheNode pre = node.pre;
CacheNode post = node.next;
pre.next = post;
if (post != null)
post.pre = pre;
positionNodes.remove(node.key);

}
}
``````

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