LFU Cache 370 ms clean Java solution with Maps

  • 0

    Free to look at this solution for inspiration. Any suggestions and corrections are welcomed!

    private final Map<Integer, FreqValue> keyValueCache = new HashMap<>();
    // queue ensures the first added (LRU) key will be removed from the cache
    private final NavigableMap<Integer, Queue<Integer>> freqKeys = new TreeMap<>();
    private final int capacity;
    private final int NO_KEY = -1;
    private class FreqValue {
    	int freq = 0;
    	int value;
    public LFUCache(int capacity) {
    	this.capacity = capacity;
    public int get(int key) {
    	if (keyValueCache.containsKey(key)) {
    		updateFreqFor(key, keyValueCache.get(key));
    		return keyValueCache.get(key).value;
    	return NO_KEY;
    public void set(int key, int value) {
    	if (keyValueCache.size() >= capacity && capacity > 0 && !keyValueCache.containsKey(key))		
    	if(keyValueCache.size() < capacity || keyValueCache.containsKey(key)){
    		updateCacheWith(key, value);
    		updateFreqFor(key, keyValueCache.get(key));
    public void removeLRUEntry(){
    	Queue<Integer> q = freqKeys.firstEntry().getValue();
    		if (!q.isEmpty())
    private void updateFreqFor(Integer key, FreqValue fv) {
    	if (freqKeys.containsKey(fv.freq)) {
    		Queue<Integer> q = freqKeys.get(fv.freq);
    		if(!q.isEmpty()) q.remove(key);
    		if(q.isEmpty()) freqKeys.remove(fv.freq);
    	if (!freqKeys.containsKey(fv.freq)) freqKeys.put(fv.freq, new LinkedList<>());
    private void updateCacheWith(int key, int value) {
    	FreqValue fv = new FreqValue();
    	if (keyValueCache.containsKey(key)) fv = keyValueCache.get(key);
    	fv.value = value;
    	keyValueCache.put(key, fv);

Log in to reply

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