Examples

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:  LRUCache lRUCache = new LRUCache(2);  
lRUCache.put(1, 1); // cache is {1=1}  
lRUCache.put(2, 2); // cache is {1=1, 2=2}  
lRUCache.get(1);   // return 1  
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}  
lRUCache.get(2);   // returns -1 (not found)  
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}  
lRUCache.get(1);   // return -1 (not found)  
lRUCache.get(3);   // return 3  
lRUCache.get(4);   // return 4  

Example 2:  
Input:  
["LRUCache", "put", "put", "get", "put", "get", "put", "get"]  
[[1], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [3]]  
Output:  [null, null, null, -1, null, -1, null, -1]  
Explanation:  LRUCache lRUCache = new LRUCache(1);  
lRUCache.put(1, 1); // cache is {1=1}  
lRUCache.put(2, 2); // evicts key 1, cache is {2=2}  
lRUCache.get(1);   // returns -1 (not found)  
lRUCache.put(3, 3); // evicts key 2, cache is {3=3}  
lRUCache.get(2);   // returns -1 (not found)  
lRUCache.put(4, 4); // evicts key 3, cache is {4=4}  
lRUCache.get(3);   // returns -1 (not found)

Disclaimer: Here is the practice link to help you assess your knowledge better. It's highly recommend trying to solve it before looking at the solution.

Approach

Algorithm

The intuition behind an LRU (Least Recently Used) Cache is that we want to store only a fixed number of items in memory and quickly evict the item that hasn’t been used for the longest time. This is useful when memory is limited and we want to keep the most relevant data available for fast retrieval. The key idea is to maintain quick lookups to check if a value exists in the cache, and also maintain the usage order so we can remove the least recently used item efficiently when the cache is full.

To implement it efficiently, we combine two data structures: a HashMap for O(1) lookup of keys, and a Doubly Linked List to maintain the order of usage. The most recentl