Concise solution with three HashMaps O(1)


  • 0
    S

    The idea is to keep three hashmaps. One to map key to value, one to map key to count, and the last one maps count to a linkedhashset of keys. Also, I keep a integer min to keep track of the minimum count. Every time we meet a set or get operation, we just update each map, and check whether we need to change min. For example, in get operation, we check whether the key we are getting has the min count and whether that key is the only one with min count. If yes, we update min by 1. Same idea goes with set operation.

    Here is the code:

    public class LFUCache {
        
        HashMap<Integer, Integer> keyToValue;
        HashMap<Integer, Integer> keyToCounts;
        HashMap<Integer, LinkedHashSet<Integer>> countsToKey;
        int capacity;
        int minCount;
    
        public LFUCache(int capacity) {
            this.capacity = capacity;
            this.minCount = 0;
            this.keyToValue = new HashMap<Integer, Integer>();
            this.keyToCounts = new HashMap<Integer, Integer>();
            this.countsToKey = new HashMap<Integer, LinkedHashSet<Integer>>();
        }
        
        public void increaseCount(int key) {
            int count = keyToCounts.get(key);
            keyToCounts.put(key, count + 1);
            if (!countsToKey.containsKey(count + 1)) countsToKey.put(count + 1, new LinkedHashSet<Integer>());
            countsToKey.get(count + 1).add(key);
            countsToKey.get(count).remove(key);
            if (minCount == count && countsToKey.get(count).size() == 0) minCount++;
        }
        
        public void removeTail() {
            int toBeRemoved = countsToKey.get(minCount).iterator().next();
            keyToValue.remove(toBeRemoved);
            keyToCounts.remove(toBeRemoved);
            countsToKey.get(minCount).remove(toBeRemoved);        
        }
        
        public int get(int key) {
            if (!keyToValue.containsKey(key)) return -1;
            increaseCount(key);
            return keyToValue.get(key);
        }
        
        public void set(int key, int value) {
            if (capacity <= 0) return;
            if (keyToValue.containsKey(key)) {
                keyToValue.put(key, value);
                increaseCount(key);
            }
            else {
                if (capacity <= keyToValue.size()) {
                    removeTail();
                }
                keyToValue.put(key, value);
                keyToCounts.put(key, 1);
                minCount = 1;
                if (!countsToKey.containsKey(1)) countsToKey.put(1, new LinkedHashSet<Integer>());
                countsToKey.get(1).add(key);
            }
        }
    }
    

    The two functions: increaseCount() and removeTail(), are to help update the maps and min. Let me know if you have any suggestions.


  • 0
    S

    great solution. clean and precise


Log in to reply
 

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