LFU Cache

Table of Contents +

LFU Cache is the harder cousin of LRU Cache. Now eviction is based on how often a key is used, not how recently. Tracking counts and still keeping every operation fast is tricky. The interviewer wants to see if you can design that with care.

🎯 The Problem

You build a cache that throws out the key used the fewest times. Here are the rules.

  • A cache is a small fast store with limited room.
  • LFU stands for Least Frequently Used.
  • When it fills up, drop the key used the fewest times.
  • If two keys tie on count, drop the one used least recently among them.
  • get(key) returns the value, or -1 if missing.
  • put(key, value) saves a key and value.
  • Both get and put count as a use, so they raise the key’s count.
  • Both must run in O(1) time.
Capacity = 2


put(1, 1)      counts: {1:1}
put(2, 2)      counts: {1:1, 2:1}
get(1)  -> 1   counts: {1:2, 2:1}
put(3, 3)      evicts key 2 (count 1, lowest)   counts: {1:2, 3:1}
get(2)  -> -1  (2 was evicted)
get(3)  -> 3   counts: {1:2, 3:2}
put(4, 4)      evicts key 1 (count 2, but oldest at that count) counts: {3:2, 4:1}
get(1)  -> -1
get(3)  -> 3
get(4)  -> 4

After put(4,4), both key 1 and key 3 have count 2. So we break the tie by recency. Key 1 was last touched before key 3, so key 1 is dropped.

Here is the order of operations and what each call returns.

put(1,1)

put(2,2)

get(1) returns 1, count of 1 is now 2

put(3,3) evicts key 2

get(2) returns -1

get(3) returns 3, count of 3 is now 2

put(4,4) evicts key 1, the oldest at count 2

get(1) returns -1

get(3) returns 3

get(4) returns 4

🐢 Approach 1: Scan For the Minimum (Brute Force)

The idea in one line: store every key with its count, then search for the smallest count on eviction.

The idea:

  • Keep each key together with its use count.
  • When the cache is full, look at every key.
  • Find the one with the smallest count and remove it.

Why it is weak:

  • Scanning all keys is O(n) per eviction, where n is the number of keys.
  • The interviewer wants O(1).
  • So we need a structure that hands us the least used key with no search.

Here is the scan-for-min-frequency code:

lfu_cache_scan.py
class LFUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.time = 0
        self.data = {}


    def get(self, key):
        if key not in self.data:
            return -1
        value, freq, _ = self.data[key]
        self.time += 1
        self.data[key] = (value, freq + 1, self.time)
        return value


    def put(self, key, value):
        if self.capacity == 0:
            return
        self.time += 1
        if key in self.data:
            _, freq, _ = self.data[key]
            self.data[key] = (value, freq + 1, self.time)
            return
        if len(self.data) == self.capacity:
            victim = min(self.data, key=lambda k: (self.data[k][1], self.data[k][2]))
            del self.data[victim]
        self.data[key] = (value, 1, self.time)

⚡ Approach 2: Frequency Buckets (Best)

The idea in one line: group keys by their use count so the lowest bucket gives the victim at once.

The idea:

  • Group keys into frequency buckets. One bucket per use count.
  • Bucket 1 holds keys used once. Bucket 2 holds keys used twice. And so on.
  • Inside each bucket, keep recency order. Newest at the front, oldest at the back.
  • The back of the lowest bucket is the key to drop on a tie.

How it works:

  • Keep a key-to-node map so lookups are instant.
  • Keep a count-to-bucket map. Track minFreq, the smallest count any key has now.
  • To evict, go straight to the bucket at minFreq and remove its back node. No scan.
  • When a key is used, move its node to the bucket one higher.
  • If that emptied the minFreq bucket, raise minFreq by one.
  • A new key starts at count 1, so on every fresh insert minFreq resets to 1.

Why it is fast:

  • Every step is a direct map lookup or a pointer move.
  • There is no scan anywhere.
  • So get and put both run in O(1).

This is the bucket structure. Each count points to a list of keys with that count, newest at the front.

count 1

key 3 (newest)

count 2

key 1 (older)

key 5 (newer)

minFreq = 1

map: key -> node

Steps to Solve

  1. Keep a key-to-node map, a count-to-bucket map, and a minFreq value.
  2. For get, if the key is missing return -1. Otherwise read its value and bump its count.
  3. To bump a count, move the node from its current bucket to the bucket one higher.
  4. If the old bucket was the minFreq bucket and is now empty, raise minFreq by one.
  5. For put, if the cache is full first evict the back node of the minFreq bucket.
  6. Insert the new key into bucket 1 and set minFreq to 1.

This Python version uses dictionaries for the value and count maps, and an OrderedDict per count to keep recency order with O(1) removal.

lfu_cache.py
from collections import OrderedDict, defaultdict




class LFUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.min_freq = 0
        self.values = {}                      # key -> value
        self.freqs = {}                       # key -> count
        self.buckets = defaultdict(OrderedDict)  # count -> keys, oldest first


    def _bump(self, key):                     # raise a key's count by one
        f = self.freqs[key]
        del self.buckets[f][key]              # remove from old bucket
        if not self.buckets[f]:               # bucket now empty
            del self.buckets[f]
            if self.min_freq == f:
                self.min_freq += 1
        self.freqs[key] = f + 1
        self.buckets[f + 1][key] = True       # newest goes to the end


    def get(self, key):
        if key not in self.values:
            return -1
        self._bump(key)
        return self.values[key]


    def put(self, key, value):
        if self.capacity == 0:
            return
        if key in self.values:                # update and bump
            self.values[key] = value
            self._bump(key)
            return
        if len(self.values) == self.capacity:     # evict oldest at min_freq
            victim, _ = self.buckets[self.min_freq].popitem(last=False)
            if not self.buckets[self.min_freq]:
                del self.buckets[self.min_freq]
            del self.values[victim]
            del self.freqs[victim]
        self.values[key] = value
        self.freqs[key] = 1
        self.buckets[1][key] = True
        self.min_freq = 1




cache = LFUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1))   # 1
cache.put(3, 3)       # evicts key 2
print(cache.get(2))   # -1
print(cache.get(3))   # 3
cache.put(4, 4)       # evicts key 1
print(cache.get(1))   # -1
print(cache.get(3))   # 3
print(cache.get(4))   # 4

The output of the above code will be:

1
-1
3
-1
3
4

Let us read the Python version line by line, because the bucket bookkeeping is the whole challenge.

We keep three structures. values maps a key to its value. freqs maps a key to its current count. buckets maps a count to an OrderedDict of keys. An OrderedDict is a dictionary that remembers the order keys were added. So the oldest key in a bucket sits at the front and the newest at the back. We also track min_freq, the smallest count any key has right now.

_bump(key) raises a key’s count. It reads the old count f, deletes the key from bucket f, and if that bucket is now empty it removes the bucket. If the emptied bucket was the min_freq bucket, we raise min_freq by one, because no key sits at the old minimum anymore. Then we set the new count and add the key to bucket f + 1. Adding to an OrderedDict puts it at the back, marking it as most recent in that bucket.

get returns -1 if the key is missing. Otherwise it bumps the count and returns the value.

put first handles a full cache. We call popitem(last=False) on the min_freq bucket. That removes the front item, which is the oldest key at the lowest count. So it respects both rules at once. The least frequent count comes from min_freq, and the oldest within that bucket comes from the front. Then we add the new key at count 1 and reset min_freq to 1, because a fresh key always starts at count 1.

⏱️ Time and Space Complexity

The scan-for-minimum version is slow because each eviction walks all keys, which is O(n). The frequency-bucket design uses maps and ordered lists so every step is direct. There is no scan. So get and put both run in O(1). The extra space is O(n) for the maps and the bucket lists.

Approach Time Complexity Space Complexity
Scan for the minimum count O(n) per eviction O(n)
Frequency buckets + ordered lists O(1) per operation O(n)

Tip

The clean trick is the min_freq value. It points straight at the bucket to evict from, so you never search for the least used key. Keep it correct on every bump and every insert.

🧩 Key Takeaways

  • ✅ LFU drops the key with the smallest use count, and breaks ties by least recent use.
  • ✅ Group keys into frequency buckets, one bucket per use count.
  • ✅ Inside each bucket keep recency order, so the oldest at that count is easy to drop.
  • ✅ Track min_freq so eviction goes straight to the right bucket with no scan.
  • ✅ A fresh key always starts at count 1, so reset min_freq to 1 on every new insert.

Check Your Knowledge

 4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

  1. 1

    In an LFU cache, which key is evicted when the cache is full?

    Why: LFU drops the least frequently used key, and ties are broken by least recent use.

  2. 2

    What is a frequency bucket?

    Why: Each bucket groups together every key that currently shares the same use count.

  3. 3

    Why do we keep recency order inside each frequency bucket?

    Why: When several keys share the lowest count, we drop the one used least recently among them.

  4. 4

    What does the min_freq value let us do?

    Why: min_freq points right at the lowest-count bucket, so eviction needs no search and stays O(1).

Score: 0 / 4

🚀 What’s Next?

Previous Reverse Nodes in k-Group Next Insert into a Sorted Circular Linked List