Design a Least Frequently Used (LFU) Cache with O(1) Operations

Design and implement a data structure for a least frequently used (LFU) cache.

Implement a class LFUCache with the following operations:

• LFUCache(int capacity) — initializes the cache with a positive integer capacity.
• int get(int key) — returns the value associated with key if it exists in the cache; otherwise returns -1.
• void put(int key, int value) — if key already exists, updates its value. Otherwise, inserts the key–value pair. If inserting the new pair would exceed capacity, the cache must first evict the least frequently used key. If two or more keys are tied for the lowest use frequency, evict the least recently used key among them.

Frequency rules:

• A key's use counter is set to 1 when it is inserted with put.
• Every subsequent get or put on an existing key increments its use counter by 1.
• When a key is evicted and later re-inserted, its counter starts again at 1.

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

Example:

LFUCache cache = new LFUCache(2);
cache.put(1, 10); // cache = {1: 10}, freq(1) = 1
cache.put(2, 20); // cache = {1: 10, 2: 20}, freq(1) = 1, freq(2) = 1
cache.get(1); // returns 10; freq(1) = 2
cache.put(3, 30); // capacity full: key 2 has the lowest frequency, so evict 2
 // cache = {1: 10, 3: 30}, freq(3) = 1
cache.get(2); // returns -1 (evicted)
cache.get(3); // returns 30; freq(3) = 2
cache.put(4, 40); // keys 1 and 3 are tied at frequency 2; key 1 is the
 // least recently used of the two, so evict 1
 // cache = {3: 30, 4: 40}
cache.get(1); // returns -1 (evicted)
cache.get(3); // returns 30
cache.get(4); // returns 40

Constraints:

• 1 <= capacity <= 10^4
• 0 <= key <= 10^5
• 0 <= value <= 10^9
• At most 2 * 10^5 total calls will be made to get and put.