> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# LFU Cache Python Solution with Tests

> Tested Python solution for LeetCode 460 with 15 pytest cases. Generate a practice environment with lcpy.

LeetCode 460, Hard. Topics: Hash Table, Linked List, Design, Doubly-Linked List. [View on LeetCode](https://leetcode.com/problems/lfu-cache/description/).

Generate this problem as a practice environment: tested reference solution, 15 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 460   # by problem number
lcpy gen -s lfu_cache   # by problem name
```

## Problem

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

Implement the `LFUCache` class:

* `LFUCache(int capacity)` Initializes the object with the `capacity` of the data structure.
* `int get(int key)` Gets the value of the `key` if the `key` exists in the cache. Otherwise, returns `-1`.
* `void put(int key, int value)` Update the value of the `key` if present, or inserts the `key` if not already present. When the cache reaches its `capacity`, it should invalidate and remove the **least frequently used** key before inserting a new item. For this problem, when there is a **tie** (i.e., two or more keys with the same frequency), the **least recently used** `key` would be invalidated.

A **use counter** is maintained for each key. The key with the smallest use counter is the least frequently used key. When a key is first inserted, its use counter is set to `1` (due to the `put` operation). The use counter is incremented each time `get` or `put` is called on it.

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

### Examples

```
Input
["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
[[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
lfu = LFUCache(2);
lfu.put(1, 1);   // cache=[1,_], cnt(1)=1
lfu.put(2, 2);   // cache=[2,1], cnt(2)=1, cnt(1)=1
lfu.get(1);      // return 1, cache=[1,2], cnt(2)=1, cnt(1)=2
lfu.put(3, 3);   // 2 is LFU (cnt=1 smallest), invalidate 2. cache=[3,1]
lfu.get(2);      // return -1
lfu.get(3);      // return 3, cnt(3)=2, cnt(1)=2
lfu.put(4, 4);   // tie cnt 1 and 3, 1 is LRU, invalidate 1. cache=[4,3]
lfu.get(1);      // return -1
lfu.get(3);      // return 3, cnt(3)=3, cnt(4)=1
lfu.get(4);      // return 4, cnt(4)=2, cnt(3)=3
```

### Constraints

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

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/lfu_cache/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/lfu_cache/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
from collections import OrderedDict, defaultdict


class LFUCache:
    # Time: O(1) amortized per get/put
    # Space: O(capacity)
    def __init__(self, capacity: int) -> None:
        self.capacity = capacity
        self.min_freq = 0
        self.key_to_val: dict[int, int] = {}
        self.key_to_freq: dict[int, int] = {}
        self.freq_to_keys: dict[int, OrderedDict[int, None]] = defaultdict(OrderedDict)

    def _touch(self, key: int) -> None:
        """Increment frequency of key and move it to the next frequency bucket."""
        freq = self.key_to_freq[key]
        bucket = self.freq_to_keys[freq]
        bucket.pop(key)
        if not bucket:
            if self.min_freq == freq:
                self.min_freq += 1
            del self.freq_to_keys[freq]
        new_freq = freq + 1
        self.key_to_freq[key] = new_freq
        self.freq_to_keys[new_freq][key] = None

    # Time: O(1)
    # Space: O(1)
    def get(self, key: int) -> int:
        if key not in self.key_to_val:
            return -1
        self._touch(key)
        return self.key_to_val[key]

    # Time: O(1)
    # Space: O(1)
    def put(self, key: int, value: int) -> None:
        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 least frequently used; ties broken by least recently used.
            min_bucket = self.freq_to_keys[self.min_freq]
            evict_key, _ = min_bucket.popitem(last=False)
            del self.key_to_val[evict_key]
            del self.key_to_freq[evict_key]
            if not min_bucket:
                del self.freq_to_keys[self.min_freq]
        self.key_to_val[key] = value
        self.key_to_freq[key] = 1
        self.freq_to_keys[1][key] = None
        self.min_freq = 1
```

## Complexity

| Time                       | Space       |
| -------------------------- | ----------- |
| O(1) amortized per get/put | O(capacity) |

## Tags

[NeetCode 250](/catalog/neetcode-250), [NeetCode All](/catalog/neetcode).