LRU Cache
Problem Description
Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.
Implement the LRUCache class:
LRUCache(int capacity)Initialize the LRU cache with positive sizecapacity.int get(int key)Return the value of thekeyif the key exists, otherwise return-1.void put(int key, int value)Update the value of thekeyif thekeyexists. Otherwise, add thekey-valuepair to the cache. If the number of keys exceeds thecapacityfrom this operation, evict the least recently used key.
The functions get and put must each run in O(1) average time complexity.
Example 1:
Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]
Explanation
Constraints:
- 1 <= capacity <= 3000
- 0 <= key <= 104
- 0 <= value <= 105
- At most 2 * 105 calls will be made to get and put.
Solve it on LeetCode
Approaches
1. Doubly Linked List with HashMap (Basic)
In this approach, we use a doubly linked list to maintain the order of use of the cache and a HashMap for quick access to elements. The doubly linked list maintains a list of nodes, each representing a key-value pair. The head of the list is the most recently used, and the tail is the least used.
Intuition:
- Use a doubly linked list because it provides constant time access to update and remove nodes.
- Use a HashMap to store references to the nodes of the linked list with the key-value pairs so that we can achieve O(1) time complexity for get and put operations.
- When a key is accessed or added, move it to the head of the list. This denotes that it's the most recently used.
- Upon hitting capacity, remove the node at the tail (least recently used).
Code:
- Time Complexity: O(1) for both
getandputoperations due to the constant time for hash table and linked list operations. - Space Complexity: O(capacity) for storing the elements in the cache.
2. Doubly Linked List with HashMap (Optimized)
The second approach involves the same data structures but focuses on optimizing memory usage and cleaning up code for efficiency.
Key Differences:
- Consolidate the insert and remove methods for more concise code.
- Ensure edge case handling for all corner scenarios in insert and removal of nodes.
Code:
- Time Complexity: O(1) for both
getandputoperations as we continue to have constant time hash table and linked list operations. - Space Complexity: O(capacity) for storing the elements and linked list pointers.