Constraints

• 0 <= capacity
• Keys and values fit in 32-bit signed integers.
• Each operation is either ["put", key, value] or ["get", key].
• On eviction, remove the least frequently used key; break ties by least recently used.
• If capacity == 0, every put is a no-op and every get returns -1.

Examples

Solution

def lfuCache(capacity, operations):
    from collections import defaultdict, OrderedDict

    class LFUCache:
        def __init__(self, capacity):
            self.capacity = capacity
            self.key_to_val = {}
            self.key_to_freq = {}
            self.freq_to_keys = defaultdict(OrderedDict)
            self.min_freq = 0

        def _touch(self, key):
            freq = self.key_to_freq[key]
            del self.freq_to_keys[freq][key]
            if not self.freq_to_keys[freq]:
                del self.freq_to_keys[freq]
                if self.min_freq == freq:
                    self.min_freq += 1
            self.key_to_freq[key] = freq + 1
            self.freq_to_keys[freq + 1][key] = None

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

        def put(self, key, value):
            if self.capacity <= 0:
                return
            if key in self.key_to_val:
                self.key_to_val[key] = value
                self._touch(key)
                return
            if len(self.key_to_val) >= self.capacity:
                evict_key, _ = self.freq_to_keys[self.min_freq].popitem(last=False)
                del self.key_to_val[evict_key]
                del self.key_to_freq[evict_key]
            self.key_to_val[key] = value
            self.key_to_freq[key] = 1
            self.freq_to_keys[1][key] = None
            self.min_freq = 1

    cache = LFUCache(capacity)
    result = []
    for op in operations:
        name = op[0]
        if name == "get":
            result.append(cache.get(op[1]))
        elif name == "put":
            cache.put(op[1], op[2])
            result.append(None)
    return result

Time complexity: O(1) average per get/put operation; O(M) total for M operations.. Space complexity: O(capacity) for the stored keys, values, frequency map, and per-frequency ordered key lists..

Hints

1. Maintain three maps: key -> value, key -> frequency, and frequency -> ordered collection of keys at that frequency (insertion-ordered so the front is the least recently used).
2. Track a running min_freq. When you bump a key's frequency, remove it from its old frequency bucket; if that bucket was the min_freq bucket and becomes empty, increment min_freq.
3. On insertion into a full cache, evict the front (oldest) key of the min_freq bucket, then set min_freq back to 1 for the newly inserted key.
4. An OrderedDict (or a doubly-linked list per frequency) gives O(1) insertion, removal, and oldest-key eviction, which is what keeps both operations O(1).