Leetcode 146. LRU Cache

Problem

Design and implement a data structure for a Least Frequently Used (LFU) cache. The cache should support retrieving items and inserting/updating items, with automatic eviction of the least frequently used item when the capacity is exceeded.

Your implementation should provide a class LFUCache with the following operations:

• LFUCache(capacity): Initialize the cache with a positive integer capacity
• get(key): Retrieve the value associated with the key if it exists in the cache, otherwise return -1. Each get operation increases the access frequency of the key.
• put(key, value): Insert or update the value for the given key. If the key already exists, update its value and increase its frequency. If the cache is at capacity and a new key needs to be inserted, evict the least frequently used key. If there is a tie in frequency, evict the least recently used among them.

Requirements

1. Both get and put operations must run in O(1) average time complexity
2. When the cache reaches capacity and a new key must be inserted, evict the key with the lowest access frequency
3. If multiple keys share the same lowest frequency, evict the one that was least recently used (oldest in time)
4. Every successful get operation increments the access frequency of that key
5. When a key is updated via put, its frequency is incremented (not reset)

Constraints

• 1 ≤ capacity ≤ 104
• 0 ≤ key, value ≤ 105
• At most 2 × 105 calls will be made to get and put

Examples

Example 1:

LFUCache cache = new LFUCache(2); cache.put(1, 100); // cache=\{1=100\} cache.put(2, 200); // cache=\{1=100, 2=200\} cache.get(1); // returns 100, cache=\{1=100, 2=200\}, freq(1)=1 cache.put(3, 300); // evicts key 2, cache=\{1=100, 3=300\} cache.get(2); // returns -1 (not found) cache.get(3); // returns 300, freq(3)=1 cache.put(4, 400); // evicts key 1 (freq 1, older than key 3), cache=\{3=300, 4=400\} cache.get(1); // returns -1 (not found) cache.get(3); // returns 300 cache.get(4); // returns 400

Example 2:

LFUCache cache = new LFUCache(3); cache.put(1, 10); cache.put(2, 20); cache.put(3, 30); cache.get(1); // returns 10, freq(1)=1 cache.get(1); // returns 10, freq(1)=2 cache.put(4, 40); // evicts key 2 or 3 (both have freq 0), cache has keys \{1, 3 or 4, 4 or 3\}

Hint 1: Data Structures You'll need to track both frequency information and recency information for each key. Consider using a hash map to store key-value pairs, another hash map to track frequencies, and a way to maintain ordering within each frequency level. Think about how to efficiently find the minimum frequency.

Hint 2: Frequency Buckets Organize keys into "buckets" based on their access frequency. Within each frequency bucket, maintain insertion order so you can quickly identify the least recently used key at that frequency level. Keep track of the current minimum frequency to optimize eviction.

Hint 3: Implementation Strategy Use a combination of hash maps and doubly-linked lists (or ordered dictionaries). One approach: maintain a hash map from frequency to an ordered collection of keys at that frequency. Also track each key's current frequency and value. Update the minimum frequency carefully during operations.

Full Solution `` Explanation:

The solution uses three main data structures:

1. key_value: Hash map storing key-value pairs for O(1) value lookup
2. key_freq: Hash map storing each key's current access frequency
3. freq_keys: Hash map from frequency level to an OrderedDict of keys at that frequency. OrderedDict maintains insertion order, allowing us to identify the least recently used key at each frequency level in O(1) time.

Key Operations:

• get(key): Check if key exists, return value, and call _update_freq() to increment its frequency. Time: O(1)

• put(key, value):

  • If key exists: update value and frequency
  • If at capacity: evict the first (oldest) key from the OrderedDict at min_freq
  • Insert new key at frequency 1 and set min_freq = 1
  • Time: O(1)

• _update_freq(key): Move key from its current frequency bucket to the next frequency bucket. If we emptied the min_freq bucket, increment min_freq. Time: O(1)

Time Complexity: O(1) average time for both get and put operations

Space Complexity: O(capacity) to store at most capacity keys across all data structures

The critical insight is using OrderedDict (or doubly-linked lists) within each frequency level to maintain recency order, enabling O(1) eviction of the least recently used key at the minimum frequency.