Problem Statement

Implement a cache that follows the Least Frequently Used (LFU) eviction policy.

When the cache reaches its capacity and a new key needs to be inserted, the key with the lowest access frequency is removed. If there is a tie (multiple keys with the same lowest frequency), the least recently used key among them is evicted.

A frequency counter is maintained for each key. It starts at 1 when a key is first inserted (via put), and increments by 1 each time get or put is called on that key.

Implement the LFUCache class:

• LFUCache(int capacity) initializes the cache with the given positive capacity.
• int get(int key) returns the value associated with key if it exists, otherwise returns -1.
• void put(int key, int value) inserts or updates the key-value pair. If inserting a new key would exceed the capacity, the least frequently used key is evicted first (with LRU tie-breaking).

Both get and put must run in O(1) average time complexity.

Additional information

• 1 <= capacity <= 1000
• 0 <= key <= 10000
• 0 <= value <= 10000

Example 1:

Input:
["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
[[2], [1, 10], [2, 20], [1], [3, 30], [2], [3], [4, 40], [1], [3], [4]]

Output: [null, null, null, 10, null, -1, 30, null, -1, 30, 40]

Explanation:

• put(1, 10), put(2, 20) -- both have freq=1
• get(1) -- returns 10, freq(1) becomes 2
• put(3, 30) -- cache full, key 2 has lowest freq (1), evict it
• get(2) -- returns -1 (evicted)
• get(3) -- returns 30, freq(3) becomes 2
• put(4, 40) -- keys 1 and 3 both have freq=2, but key 1 was used less recently, evict it
• get(1) -- returns -1 (evicted)
• get(3) -- returns 30
• get(4) -- returns 40

Example 2:

Input:
["LFUCache", "put", "get", "put", "get", "get"]
[[1], [1, 10], [1], [1, 20], [1], [2]]

Output: [null, null, 10, null, 20, -1]

Brute Force (Linear Scan)

Intuition

The simplest approach is to store each key along with its value, frequency, and a timestamp (or recency marker). On eviction, scan all keys to find the one with the lowest frequency (breaking ties by the oldest timestamp). This is straightforward but slow.

Algorithm

1. Store entries as {key: (value, frequency, timestamp)}.
2. On get(key): if the key exists, increment its frequency and update its timestamp. Return the value.
3. On put(key, value): if the key exists, update it. Otherwise, if at capacity, scan all entries to find the one with the minimum frequency (LRU on ties) and remove it. Insert the new key with frequency 1.

class LFUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.time = 0
        self.data = {}  # key -> [val, freq, timestamp]

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

    def put(self, key, value):
        if self.cap <= 0:
            return
        self.time += 1
        if key in self.data:
            self.data[key][0] = value
            self.data[key][1] += 1
            self.data[key][2] = self.time
            return
        if len(self.data) >= self.cap:
            min_key = min(self.data, key=lambda k: (self.data[k][1], self.data[k][2]))
            del self.data[min_key]
        self.data[key] = [value, 1, self.time]

Time & Space Complexity

• Time complexity: O(n) per put (due to linear scan for eviction), O(1) per get

• Reason: Finding the minimum frequency key requires scanning all entries.

• Space complexity: O(capacity)

• Reason: We store at most capacity entries.

Three Hash Maps (Optimal)

Intuition

To achieve O(1) for both operations, we need to instantly find: (a) the value for a key, (b) the frequency of a key, and (c) the LRU key among all keys with the minimum frequency.

We use three hash maps:

1. key_val -- maps key to value.
2. key_freq -- maps key to its current frequency.
3. freq_keys -- maps each frequency to an OrderedDict of keys at that frequency (maintaining insertion/access order for LRU tie-breaking).

We also track min_freq -- the current minimum frequency across all keys. This lets us find the eviction candidate in O(1).

Algorithm

1. On get(key): if the key exists, remove it from its current frequency group, move it to freq+1 group, update min_freq if needed, return the value.
2. On put(key, value): if the key exists, update its value and call the same frequency-update logic. If inserting new and at capacity, pop the oldest key from freq_keys[min_freq] (the LRU among the least frequent). Insert the new key at frequency 1 and set min_freq = 1.

from collections import defaultdict, OrderedDict

class LFUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.min_freq = 0
        self.key_val = {}
        self.key_freq = {}
        self.freq_keys = defaultdict(OrderedDict)

    def _update(self, key):
        freq = self.key_freq[key]
        self.freq_keys[freq].pop(key)
        if not self.freq_keys[freq] and self.min_freq == freq:
            self.min_freq += 1
        self.key_freq[key] = freq + 1
        self.freq_keys[freq + 1][key] = None

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

    def put(self, key, value):
        if self.cap <= 0:
            return
        if key in self.key_val:
            self.key_val[key] = value
            self._update(key)
            return
        if len(self.key_val) >= self.cap:
            evict_key, _ = self.freq_keys[self.min_freq].popitem(last=False)
            del self.key_val[evict_key]
            del self.key_freq[evict_key]
        self.key_val[key] = value
        self.key_freq[key] = 1
        self.freq_keys[1][key] = None
        self.min_freq = 1

Time & Space Complexity

• Time complexity: O(1) per get and put

• Reason: All operations (hash map lookup, OrderedDict pop/insert, min_freq update) are O(1).

• Space complexity: O(capacity)

• Reason: The three hash maps together store at most capacity entries plus constant overhead per frequency bucket.