• 0 <= capacity <= 10⁴
• 0 <= key <= 10⁵
• 0 <= value <= 10⁹
• At most 2 × 10⁵ calls will be made to get and put

This is LRU Cache with a harder eviction rule, so start from what changes. LRU evicts the key you touched longest ago. LFU evicts the key you've used the fewest times — it tracks a use count per key (every get and every put on a key bumps its count by one) and, when full, throws out the key with the smallest count. The catch: several keys can be tied at the lowest count. The tie-breaker is recency — among the least-frequently-used, drop the least-recently-used. So LFU is really "frequency first, recency as the tiebreaker," and everything must still be O(1).

LRU kept one recency-ordered list and evicted its back. But frequency adds a second dimension: we now need, instantly, the lowest count in the whole cache, and within that count the stalest key. One flat list can't order by two things at once and stay O(1). Scanning to find the minimum count would be O(N) — the exact trap we keep refusing.

Group keys by their current count. Keep a separate recency-ordered list for count 1, another for count 2, and so on — each behaving exactly like the LRU list you already built (freshest at the front, stalest at the back). Now the two dimensions are cleanly separated: which list you're in encodes frequency, and position within the list encodes recency. To evict, go to the lowest non-empty count's list and drop its stalest (back) element — both parts O(1) if we can find that lowest count fast.

To make every piece O(1) we hold three things:
- values: key → value (and we track each key's count).
- counts: key → current use count.
- lists: count → an ordered recency list of the keys at that count (an ordered map, so front/back access and removal are O(1)).
- min_freq: the smallest count that currently has any key — this is the shelf we evict from.

When a key is used, it graduates from count c to c + 1: remove it from the count-c list, append it to the (fresh end of the) count-c+1 list, bump its count. The only bookkeeping subtlety is min_freq: if the key we just promoted emptied the count-min_freq list, then the smallest non-empty count is now one higher, so min_freq += 1.

from collections import defaultdict, OrderedDict

class LFUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.values = {}                       # key -> value
        self.counts = {}                       # key -> use count
        self.lists = defaultdict(OrderedDict)  # count -> {key: None} in recency order
        self.min_freq = 0

    def _bump(self, key):                      # promote key from c to c+1
        c = self.counts[key]
        del self.lists[c][key]
        if not self.lists[c] and c == self.min_freq:
            self.min_freq += 1                 # that shelf emptied → min rises
        self.counts[key] = c + 1
        self.lists[c + 1][key] = None          # append = freshest at count c+1

    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.cap == 0:
            return
        if key in self.values:                 # update + count as a use
            self.values[key] = value
            self._bump(key)
            return
        if len(self.values) >= self.cap:       # full → evict LFU (ties: LRU)
            evict, _ = self.lists[self.min_freq].popitem(last=False)  # stalest at min count
            del self.values[evict]; del self.counts[evict]
        self.values[key] = value               # new keys always enter at count 1
        self.counts[key] = 1
        self.lists[1][key] = None
        self.min_freq = 1

Every operation is O(1): a fixed number of dictionary and ordered-map edits, and min_freq is maintained incrementally instead of searched. Memory is O(capacity). The big lesson generalizes past caches: when eviction (or any priority) depends on two ranked keys — a primary and a tiebreaker — bucket by the primary and keep each bucket ordered by the tiebreaker. Finding the extreme becomes "lowest bucket, then its end," both constant time. That two-level structure — LRU's map-plus-list, replicated once per frequency and indexed by a running minimum — is the standard way to squeeze a two-criteria eviction policy down to O(1).