LFU Cache

Design and implement a data structure for a Least Frequently Used (LFU) cache.

Implement a function that processes an array of operations and an array of arguments:

• "LFUCache" — Initializes the LFU cache with capacity.
• "put" — Update the value of key if it exists, otherwise insert. When capacity is reached, evict the least frequently used key. If multiple keys have the same frequency, evict the least recently used among them.
• "get" — Return the value of key if it exists, otherwise return -1. Accessing a key increases its frequency by 1.

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

Examples

Example 1:

Input: operations = ["LFUCache","put","put","get","put","get","get","put","get","get","get"], args = [[2],[1,1],[2,2],[1],[3,3],[2],[3],[4,4],[1],[3],[4]]

Output: [null,null,null,1,null,-1,3,null,-1,3,4]

Explanation: Capacity 2. put(1,1), put(2,2). get(1)=1 (freq[1]=2). put(3,3): evict key 2 (LFU, freq=1). get(2)=-1. get(3)=3. put(4,4): evict key 3 (LFU freq=1, but 3 was used more recently... wait — 3 was just accessed above. freq[3]=2, freq[1]=2. Evict the LRU among freq=2: key 1 (accessed earlier). So get(1)=-1, get(3)=3, get(4)=4.

Example 2:

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

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

Explanation: Capacity 1. put(1,10). get(1)=10 (freq[1]=2). put(2,20): evict key 1 (only key, evicted). get(1)=-1. get(2)=20.

Constraints

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