146. LRU Cache - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

Design a data structure that follows the Least Recently Used (LRU) cache policy. The cache has a fixed capacity and supports two operations: get and put.

get(key): Retrieve the value associated with key if it exists in the cache. If not found, return -1. Any successful get operation should mark the key as recently used.
put(key, value): Insert or update the value for key. If the key already exists, update its value and mark it as recently used. If the cache is at capacity and a new key needs to be added, evict the least recently used item before inserting the new key.

Constraints:

The cache capacity is a positive integer (at least 1).
Keys and values are integers (with values assumed to be positive in the problem description).
The operations should ideally run in O(1) time on average (this is hinted as a follow-up requirement).

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 cache = new LRUCache(2); // capacity 2
cache.put(1, 1); // cache is {1=1}
cache.put(2, 2); // cache is {1=1, 2=2}
cache.get(1);    // returns 1 (cache: {2=2, 1=1} – 1 is now recently used)
cache.put(3, 3); // evicts key 2 (LRU was 2), cache becomes {1=1, 3=3}
cache.get(2);    // returns -1 (2 was evicted)
cache.put(4, 4); // evicts key 1 (LRU was 1), cache becomes {4=4, 3=3}
cache.get(1);    // returns -1 (1 was evicted)
cache.get(3);    // returns 3 
cache.get(4);    // returns 4

In the above sequence, whenever the cache reached capacity, the least recently used key was removed before adding a new item.

Example 2:
Input:

["LRUCache","put","put","get","get"]
[[1],[1,10],[2,20],[1],[2]]

Output:

[null,null,null,-1,20]

Explanation:

LRUCache cache = new LRUCache(1); // capacity 1
cache.put(1, 10); // cache is {1=10}
cache.put(2, 20); // cache is at capacity, evicts key 1, cache is {2=20}
cache.get(1);     // returns -1 (key 1 was evicted)
cache.get(2);     // returns 20 (key 2 is in cache)

This shows that with capacity 1, every new insertion evicts the previous item (always the LRU because only one item can be stored at a time).

Hints

O(1) access requirement – The prompt hints that both operations should be very efficient (ideally constant time). This suggests using a hash table (dictionary) for direct key-based access in O(1) time.
Track usage order – We need to quickly update which entry is the most recently used and which is the least. Consider a data structure that can maintain an order of elements and allow fast removals and insertions from either end. A doubly linked list is a good candidate for this.
Combine data structures – A single data structure might not be enough. The common strategy is to combine a hash map and a doubly linked list: use the hash map to store references to nodes in the linked list. This way, you can find nodes by key in O(1) and also move them within the list in O(1).
Use existing libraries (optional) – In a real interview, you might be allowed to use built-in classes. For example, Java has LinkedHashMap which can be used to implement LRU by overriding a method, and Python has OrderedDict (or collections.deque with manual handling) to maintain order. However, be prepared to explain or implement the underlying mechanism using fundamental data structures (hash map + linked list), as that demonstrates understanding.

Brute Force Approach

Idea: A straightforward (but not optimal) approach is to use a hash map in conjunction with a list to track usage order. The list maintains the keys in the order of usage (e.g. oldest first or newest first). On each operation, we update this list to reflect the current usage order.

For get(key): Check if the key exists in the dictionary. If yes, return its value and also update the usage order by moving this key to the “most recent” end of the list (since it was just accessed). If the key is not found, return -1.
For put(key, value): If the key already exists, update its value and move the key to the most recent end of the list (because a put counts as access). If the key does not exist, insert it: append the key to the list (most recent end) and add it to the dictionary. If adding this new item causes the cache size to exceed capacity, remove the least recently used item (which would be at the opposite end of the list) and delete it from the dictionary.

This approach is simple but each operation may require searching or removing from a Python list (or Java ArrayList) by value or index, which is O(n) in the worst case. For example, finding and removing a specific key from the list (for updating recency) or removing the oldest element from the front of an array list takes linear time.

Complexity: In the worst case, both get and put operations run in O(n) time (where n is the number of items in the cache), because of list operations that take linear time. Space complexity is O(n) for storing up to n key-value pairs (in the list and dictionary). This fails to meet the O(1) requirement for large n, but it works functionally.

Brute-force Python Code:

Python3

. . . .

Brute-force Java Code:

Java

. . . .

Explanation: In this brute force solution, order keeps track of keys from least recently used (front of list) to most recently used (end of list). Whenever a key is accessed or updated, it’s moved to the end. When the capacity is exceeded, the key at the front of the list (least recently used) is evicted. While this approach is straightforward, operations like order.remove(key) take O(n) time due to the list traversal needed to find the key. Thus, this approach is not optimal for large caches, but it helps illustrate the concept.

Optimal Approach: Hash Map + Doubly Linked List (O(1) operations)

To achieve average O(1) time for both get and put, we can combine a hash map with a doubly linked list. The hash map provides quick access to cache entries by key, and the doubly linked list maintains the usage order of entries so we can identify and remove the LRU item in O(1).

Data Structure Design:
We use a doubly linked list where nodes represent cache entries (key and value). The list is ordered from most recently used (at one end) to least recently used (at the other end). Additionally, we maintain a hash map (cache) that maps each key to its corresponding node in the list.

Illustration: We use dummy head and tail nodes in the doubly linked list to simplify edge cases (they do not hold real data). Actual cache nodes are inserted between these sentinels. In this example diagram, the cache holds keys 4, 3, 1, 2 with 4 as the most recently used and 2 as the least recently used. The head pointer marks the recent end, and tail marks the LRU end. Using dummy nodes for head and tail makes it easier to add or remove nodes without worrying about NULL pointers at the boundaries.

Operations:

get(key): Check the hash map for the key. If not found, return -1. If found, we retrieve the node from the map, then move that node to the head of the linked list (marking it as most recently used) and return its value. Moving the node to head involves removing it from its current position and re-inserting it at the front of the list. These remove and insert operations are O(1) since we have direct pointers to the node and the list nodes are doubly linked.
put(key, value): First, check if the key already exists in the cache (hash map).
- If it exists, update the node’s value and move that node to the head of the list (since it’s now recently used). This covers the case where an existing entry is updated without changing the cache size.
- If it does not exist, create a new node for the key-value pair. Insert this new node at the head of the list (as the most recent item) and add it to the hash map. Now, if adding this new node caused the cache size to exceed capacity, we must evict the least recently used item. The LRU item will be at the tail end of the linked list (specifically, the node just before the tail dummy). We remove that node from the list and delete its entry from the hash map. This eviction is also O(1) because the tail node can be accessed in O(1) and removed in O(1).
Visualization: If the cache is full, adding a new item will evict the least recently used item. In the diagram above, capacity = 3 and the cache currently holds keys [1, 3, 2] (where 1 is most recently used and 2 is least recently used). When a new key 4 is added, key 2 (LRU) is removed, and the new key 4 is inserted at the head as the most recent item. This updates the cache to hold [4, 1, 3] where 4 is now most recent and 3 is least recent.

Using this design, both operations run in constant time on average:

The hash map lookup for get/put is O(1) on average.
Removing a node or adding it to the head of the doubly linked list is O(1) given direct references.
Removing the tail node during eviction is O(1).

There is no need for any linear scans, which satisfies the efficiency requirement.

Complexity: Both get and put operations are O(1) on average with this approach. (In worst-case, hash map operations could degrade if many collisions occur, but assuming a good hash function and sufficient capacity, it’s effectively constant time.) The space complexity is O(capacity) to store up to capacity nodes in the list and the map. We use a bit of extra space for pointers in the linked list, but that is also O(n) relative to the number of items. This optimal solution meets the problem’s requirements by trading off a more complex data structure for efficient operations.

Optimal Python Code:

Python3

. . . .

Optimal Java Code:

Java

. . . .

In both implementations above, the head dummy’s next pointer always points to the most recently used node, and the tail dummy’s prev pointer always points to the least recently used node. The helper functions _remove/remove and _insert_at_head/insertAtHead encapsulate the list operations for clarity. By adjusting pointers, we can move nodes in O(1) time. The hash map cache stores references to the nodes, so we can access any node by key in O(1) and then remove or move it in O(1) as well.

Step-by-Step Walkthrough Example

Let’s walk through Example 1 (capacity = 2) using the optimal LRU cache to visualize how the state changes after each operation:

LRUCache(2) – Initialize an empty cache with capacity 2. (Initially, cache = {} empty.)
put(1, 1) – Cache was empty, insert key 1 with value 1.
State: Cache contains {1=1}. (1 is most recently used, also the only item.)
put(2, 2) – Insert key 2 with value 2.
State: Cache contains {1=1, 2=2}. Now 2 is the most recently used and 1 is the least recently used (because 1 was added before 2 and hasn’t been accessed since).
get(1) – Access key 1. It exists, returns 1. Mark key 1 as most recently used by moving it to the front of the list.
Output: 1
State: Cache is {2=2, 1=1} where 1 is now most recent. (Key 2 becomes least recently used since 2 was not accessed as recently as 1.)
put(3, 3) – Cache is at capacity (2). We need to insert key 3. The least recently used key is 2 (from state above). Evict key 2, then insert {3=3}.
State: Cache becomes {1=1, 3=3}. Key 3 is most recent (just added), key 1 is least recent.
(Eviction: key 2 was removed, as it was the LRU.)
get(2) – Try to access key 2. Key 2 was evicted in the previous step, so it’s no longer in cache.
Output: -1 (not found)
State: Cache remains {1=1, 3=3}.
put(4, 4) – Cache is at capacity. We need to insert key 4, so evict the LRU item. Currently, keys {1, 3} are in cache with 1 as LRU (since 3 was added more recently). Evict key 1, then insert {4=4}.
State: Cache becomes {3=3, 4=4}. Key 4 is most recent, key 3 is now least recent.
get(1) – Try to access key 1. It was evicted in the previous step.
Output: -1 (not found)
State: Cache remains {3=3, 4=4}.
get(3) – Access key 3. It exists, return 3, and mark 3 as most recently used. (Move key 3 to front of list.)
Output: 3
State: Cache becomes {4=4, 3=3} (now 3 is most recent, 4 is least recent).
get(4) – Access key 4. It exists, return 4, and mark 4 as most recently used.
Output: 4
State: Cache becomes {3=3, 4=4} (4 is most recent again, 3 is least).

The output sequence from the get operations would be [1, -1, -1, 3, 4], which matches the expected result. This walkthrough demonstrates how the LRU cache always evicts the least recently used item when full and updates the order on every access.

Common Mistakes

Forgetting to update usage order: A frequent bug is to retrieve a value on get without moving that key to the most recent position. This breaks the LRU logic – make sure every cache hit in get (and every insertion/update in put) updates the order of items. If you don’t move the accesssed node, the cache will evict the wrong item later.
Improperly handling existing keys on put: If a key already exists, you should update its value and move it to the front. Some might forget to move the node, or conversely, mistakenly evict something when updating an existing key. Remember that updating an existing key does not change the size of the cache, it should not trigger an eviction.
Mistakes in doubly linked list operations: Pointers must be updated carefully. Forgetting to re-link a node’s neighbors when removing a node, or inserting a node incorrectly (e.g., not updating head/tail pointers) can break the structure. Using dummy head/tail sentinels greatly simplifies this logic. Without sentinels, you need extra checks for when the list is empty or when removing the first/last element. Off-by-one errors in pointer updates are common, so double-check the remove and insert logic.
Not removing evicted keys from the map: If you evict a node from the linked list but forget to remove its entry from the hash map, your cache will still report that key as present. This leads to incorrect get results or memory leaks. Always delete the evicted key from the map.
Using the wrong data structures: Some try to use a singly linked list or other structures that don’t allow O(1) removal of an arbitrary node. A singly linked list, for example, cannot remove a middle node in O(1) because you need the node’s previous pointer. That’s why a doubly linked list is preferred. Similarly, trying to use a regular array or list for ordering (as in the brute force approach) leads to O(n) updates. Ensure your data structure choices align with the O(1) operations requirement.

Edge Cases to Consider

Capacity = 1: The cache can only hold one item at a time. Every new put (if the key is different) should evict the existing item. Make sure this scenario works correctly (your code should always evict the old item when adding a new one if capacity is 1). Example: put(1,val), then put(2,val) should remove key 1. This is a good simple test for your implementation.
Access patterns with no evictions: If the number of put operations never exceeds capacity (e.g., capacity 5 but you only added 3 items), then no eviction should occur. Ensure that in such cases your cache simply stores the items and returns them correctly. There’s no eviction to test here, but it’s important that normal operations don’t misbehave (e.g., your code shouldn’t try to evict when it’s not necessary).
Consecutive get calls on the same key: Repeated get(x) on the same key should always return the same value (assuming no interim put changes it), and after the first access, further accesses shouldn’t change the order because x is already most recently used. Test that calling get twice in a row doesn’t cause an error (your code might try to move the node that is already at head, so it should handle that gracefully, effectively doing nothing visible).
Updating an existing key’s value: When a put updates an existing key’s value, ensure the capacity doesn’t change and no eviction occurs. The item should just move to most recent. For example, if cache contains {1=1, 2=2} and capacity is 2, a call to put(1, 10) should update key 1’s value to 10 and mark 1 as most recent (so key 2 becomes LRU), but the cache size stays 2 and no item is evicted. Then a new put of a different key would evict key 2.
get on a non-existent key: Should simply return -1 and not alter the state of the cache. Ensure that this does not accidentally remove anything or cause errors.
High frequency of operations: The solution should handle sequences of operations where the cache is frequently filled and emptied. The data structure should remain consistent after many evictions and insertions. This is more about performance: ensure that your approach indeed operates in O(1) for large sequences (the brute force approach would start timing out as the number of operations grows large).

(Note: The problem guarantee is that capacity ≥ 1, so we do not need to handle cases where capacity is 0. If capacity were 0, get should always return -1 and put would never store anything.)

Alternative Variations

Using built-in Ordered Dictionaries/LinkedHashMap: Many languages offer built-in data structures that simplify LRU cache implementation. For instance, Python’s collections.OrderedDict can be used with its move_to_end() method to mark items as recent and popitem to evict LRU. In Java, LinkedHashMap can maintain insertion order or access order automatically; by subclassing it and overriding removeEldestEntry, one can implement an LRU cache with minimal code. These approaches are essentially the same logic but leveraged via library features. In an interview, using these might be acceptable, but be ready to explain the underlying mechanism (which is still a hash map + linked list internally).
Fixed time-to-live (TTL) cache or Time-based eviction: A different variation is a cache that evicts entries not just by recency but by an expiration time. This would require tracking timestamps and periodically removing expired entries. It’s not the same as LRU, but interviewers might ask how to handle expiration on top of LRU.
Most Recently Used (MRU) Cache: The opposite policy of LRU – evict the most recently used item first. This is less common, but conceptually you could implement it by always evicting from the front of the list (if you kept most recent at front) instead of the back. Essentially just a tweak in policy.
LFU Cache (Least Frequently Used): Instead of recency, evict the item that has been used least often. This is a different LeetCode problem (LFU Cache) and is more complex (often using a combination of hash map and min-heap or multiple lists). It’s a distinct variation of the cache eviction problem.
Thread-safe LRU Cache: In a real-world scenario or design interview, you might be asked how to make the LRU cache support concurrent access (multiple threads). This would involve locking or using thread-safe data structures. The fundamental logic remains the same, but you’d need to ensure mutual exclusion when updating the cache.
Multi-level caches: Sometimes systems have two levels of cache (like L1 and L2 in CPUs) with an LRU policy at each. An interview might not ask you to implement this, but understanding LRU helps in system design discussions about caching at multiple levels.

To further reinforce your understanding, you can practice these related LeetCode problems and design questions:

460. LFU Cache (Hard) – Design a cache that evicts the least-frequently used item. It combines the ideas of caching and frequency counting. (It requires a data structure like LRU but extended to account for frequencies.)
432. All O`one Data Structure (Hard) – Design a data structure with O(1) operations for incrementing, decrementing, and getting max/min keys. This also uses a combination of hash maps and linked lists/double-linked nodes to achieve O(1) updates.
588. Design In-Memory File System (Hard) – While not about caching, this is a design problem that uses tree/tries and requires managing data structures efficiently. It’s mentioned here because it’s a design-intensive problem (like LRU cache) and often listed alongside LRU in practice guides.
146. LRU Cache (Medium) – (The problem we just discussed.) Re-implement it without looking at solutions to test your understanding.
155. Min Stack (Easy) – Design a stack that supports retrieving the minimum element in O(1). This is a simpler design problem using two stacks. It’s not directly related to LRU, but it’s another example of augmenting a data structure for efficient queries (just as we augmented a cache with ordering).
362. Design Hit Counter (Medium) – Design a hit counter which counts hits in the past 5 minutes. It uses a queue or circular buffer to evict old hits as time passes. The idea of evicting old data in O(1) time is conceptually similar to how LRU evicts old entries (though the criteria is time-based instead of usage-based).

146. LRU Cache - Detailed Explanation

Problem Statement

Hints

Brute Force Approach

Optimal Approach: Hash Map + Doubly Linked List (O(1) operations)

Step-by-Step Walkthrough Example

Common Mistakes

Edge Cases to Consider

Alternative Variations

Related Problems