grid47 Exploring patterns and algorithms
Oct 23, 2024
7 min read
Solution to LeetCode 146: LRU Cache Problem
Design and implement an LRU (Least Recently Used) cache. The cache should support two operations: get(key) and put(key, value). Both operations must run in O(1) time on average. If the cache exceeds its capacity, the least recently used key should be evicted.
Problem
Approach
Steps
Complexity
Input: The input consists of a series of operations on the LRUCache. The operations include initializing the cache with a given capacity and executing `get` and `put` commands.
• The output for each operation is either the return value of `get(key)` or null for `put(key, value)`.
Goal: Design a data structure that efficiently handles `get` and `put` operations with O(1) average time complexity.
Steps:
• Use a hash map to store the key-value pairs for O(1) lookups.
• Use a doubly linked list to maintain the order of use of keys, where the most recently used key is at the front and the least recently used is at the back.
• On `put`, add the key-value pair to the cache and move it to the front. If the cache exceeds capacity, evict the least recently used key from the back.
Goal: The implementation must ensure that both `get` and `put` operations run in O(1) average time.
Steps:
• Capacity is a positive integer and will not exceed 3000.
• The cache must efficiently handle up to 2 * 10^5 operations.
Assumptions:
• The cache will only contain integer keys and values.
• The input operations will be well-formed and within the constraints.
• Explanation: In this example, the cache is initialized with a capacity of 2. The operations are performed as described, with key-value pairs being added to the cache and the least recently used keys being evicted when necessary.
Approach: We can solve this problem using a combination of a hash map and a doubly linked list to maintain the cache and manage eviction of the least recently used key.
Observations:
• The most challenging part is ensuring that both `get` and `put` operations run in O(1) time.
• A hash map will provide O(1) access to values, while a doubly linked list will help us manage the order of access.
• The doubly linked list allows us to efficiently add and remove nodes, and the hash map allows for fast lookups.
Steps:
• 1. Initialize a doubly linked list to track the order of keys and a hash map for fast lookups.
• 2. When `get(key)` is called, move the key to the front of the list if it exists.
• 3. When `put(key, value)` is called, add the key-value pair to the front of the list, and evict the least recently used key from the back if the cache exceeds capacity.
Empty Inputs:
• Ensure that operations on an empty cache handle edge cases, such as requesting a value that doesn't exist.
Large Inputs:
• Handle large numbers of operations efficiently within the time and space constraints.
Special Values:
• Ensure that key-value pairs with edge values (e.g., 0, 10^5) are handled properly.
Constraints:
• The solution must meet time and space complexities within the provided constraints.
map<int, list<pair<int, int>>::iterator> mp;
list<pair<int, int>> q;
int cap;
LRUCache(int capacity) {
cap = capacity;
}
intget(int key) {
if(!mp.count(key)) return-1;
auto it =*mp[key];
q.erase(mp[key]);
q.push_front(make_pair(key, it.second));
mp[key] = q.begin();
return it.second;
}
voidput(int key, int value) {
if(mp.count(key)) {
q.erase(mp[key]);
q.push_front(make_pair(key, value));
mp[key] = q.begin();
} else {
q.push_front(make_pair(key, value));
mp[key] = q.begin();
if(q.size() > cap) {
mp.erase(q.back().first);
q.pop_back();
}
}
}
};
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache* obj = new LRUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
1 : Variable Declaration
map<int, list<pair<int, int>>::iterator> mp;
Declares a map `mp` that stores iterators to a doubly linked list. This map is used to quickly locate the nodes by their keys.
2 : List Declaration
list<pair<int, int>> q;
Declares a doubly linked list `q` where each node stores a key-value pair. This list maintains the order of access from the most recently used (front) to the least recently used (back).
3 : Variable Declaration
int cap;
Declares an integer `cap` to hold the maximum capacity of the LRU Cache.
4 : Constructor
LRUCache(int capacity) {
Constructor for the LRUCache class, initializing the cache with a given capacity.
5 : Initialize Capacity
cap = capacity;
Sets the `cap` variable to the provided capacity, which limits the number of items the cache can hold.
6 : Function Definition
intget(int key) {
Defines the `get` function, which retrieves the value associated with the given key if it exists in the cache.
7 : Check If Key Exists
if(!mp.count(key)) return-1;
Checks if the key exists in the map. If not, returns -1 to indicate the key is not found.
8 : Retrieve Value
auto it =*mp[key];
Retrieves the iterator to the node in the list corresponding to the given key.
9 : Move Node to Front
q.erase(mp[key]);
Erases the current node from its position in the list, as it needs to be moved to the front to mark it as recently used.
10 : Reinsert Node
q.push_front(make_pair(key, it.second));
Inserts the key-value pair at the front of the list to mark it as the most recently used.
11 : Update Map
mp[key] = q.begin();
Updates the map with the new iterator pointing to the front of the list for the given key.
12 : Return Value
return it.second;
Returns the value associated with the key.
13 : Function Definition
voidput(int key, int value) {
Defines the `put` function, which inserts a key-value pair into the cache, or updates an existing key.
14 : Check If Key Exists
if(mp.count(key)) {
Checks if the key already exists in the cache.
15 : Update Existing Node
q.erase(mp[key]);
Erases the old entry for the key from the list.
16 : Reinsert Node
q.push_front(make_pair(key, value));
Inserts the key-value pair at the front of the list to mark it as the most recently used.
17 : Update Map
mp[key] = q.begin();
Updates the map with the new iterator pointing to the front of the list for the given key.
18 : Handle New Key
} else {
If the key does not already exist in the cache, handle it as a new key-value pair.
19 : Insert New Node
q.push_front(make_pair(key, value));
Inserts the new key-value pair at the front of the list.
20 : Update Map
mp[key] = q.begin();
Updates the map with the new iterator pointing to the front of the list for the given key.
21 : Evict Least Recently Used
if(q.size() > cap) {
Checks if the size of the list exceeds the cache's capacity.
22 : Remove Least Recently Used
mp.erase(q.back().first);
Erases the least recently used item (at the back of the list) from both the list and the map.
23 : Pop Back
q.pop_back();
Removes the last element from the list, which is the least recently used key-value pair.
Best Case: O(1)
Average Case: O(1)
Worst Case: O(1)
Description: Both `get` and `put` operations will run in constant time due to the use of a hash map for lookups and a doubly linked list for order management.
Best Case: O(capacity)
Worst Case: O(capacity)
Description: The space complexity is proportional to the cache's capacity, as each key-value pair takes up space in the cache.
