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


  • 3
    S

    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, LinkedHashMap<Integer, Integer>> freqToEntry;
        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);
                freqToEntry.computeIfAbsent(freq+1, x->new LinkedHashMap<>()).put(key, value);
                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);
                freqToEntry.computeIfAbsent(freq+1, x->new LinkedHashMap<>()).put(key, value);
                if(freq==min && freqToEntry.get(freq).size()==0) min = min+1;
            }else{
                if(keyToFreq.size()==capacity) removeOldest();
                keyToFreq.put(key, 1);
                freqToEntry.computeIfAbsent(1, x->new LinkedHashMap<>()).put(key, value);
                min = 1;
            }
        }
        
        private void removeOldest(){
            int rmKey = freqToEntry.get(min).keySet().iterator().next();
            keyToFreq.remove(rmKey);
            freqToEntry.get(min).remove(rmKey);
        }
    }
    
    

Log in to reply
 

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