460. LFU Cache

Intuition

Least-Frequently-Used evicts the key with lowest access count (ties broken by LRU). Maintain: key→(value,freq), freq→LinkedHashSet of keys, and a minFreq counter.

Algorithm

1On get(key): if present, increment its freq, move it to the new freq set, update minFreq. Return value.
2On put(key,val): if capacity 0, return. If key exists, update value and call get logic. If at capacity, evict: remove oldest key from freq[minFreq] set. Insert key at freq 1, set minFreq=1.

Common Pitfalls

•Use LinkedHashSet to maintain insertion order within same frequency (for LRU tie-breaking).
•Reset minFreq to 1 on every new insert.

460.cs

// Approach: Track minFreq; HashMap key→freq and freq→LRU-ordered-keys;
// on eviction remove the LRU entry from the minFreq bucket.
// Time: O(1) per get/put Space: O(capacity)

public class LFUCache
{
    private int capacity;
    private int minFreq = 0;
    private Dictionary<int, int> keyToVal = new Dictionary<int, int>();
    private Dictionary<int, int> keyToFreq = new Dictionary<int, int>();
    private Dictionary<int, LinkedList<int>> freqToLRUKeys = new Dictionary<int, LinkedList<int>>();

    public LFUCache(int capacity)
    {
        this.capacity = capacity;
    }

    public int Get(int key)
    {
        if (!keyToVal.ContainsKey(key))
            return -1;

        int freq = keyToFreq[key];
        freqToLRUKeys[freq].Remove(key);
        if (freq == minFreq && freqToLRUKeys[freq].Count == 0)
        {
            freqToLRUKeys.Remove(freq);
            ++minFreq;
        }

        // Increase key's freq by 1
        // Add this key to next freq's list
        PutFreq(key, freq + 1);
        return keyToVal[key];
    }

    public void Put(int key, int value)
    {
        if (capacity == 0)
            return;
        if (keyToVal.ContainsKey(key))
        {
            keyToVal[key] = value;
            Get(key); // Update key's count
            return;
        }

        if (keyToVal.Count == capacity)
        {
            // Evict an LRU key from `minFreq` list.
            int keyToEvict = freqToLRUKeys[minFreq].First.Value;
            freqToLRUKeys[minFreq].RemoveFirst();
            keyToVal.Remove(keyToEvict);
        }

        minFreq = 1;
        PutFreq(key, minFreq);    // Add new key and freq
        keyToVal[key] = value;    // Add new key and value
    }

    private void PutFreq(int key, int freq)
    {
        keyToFreq[key] = freq;
        if (!freqToLRUKeys.ContainsKey(freq))
        {
            freqToLRUKeys[freq] = new LinkedList<int>();
        }
        freqToLRUKeys[freq].AddLast(key);
    }
}

/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache obj = new LFUCache(capacity);
 * int param_1 = obj.Get(key);
 * obj.Put(key,value);
 */

Was this solution helpful?