LRU Cache

Explanation & Solution

Practice Problem

Description

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement a function that processes an array of operations and an array of arguments:

"LRUCache" — Initialize the LRU cache with positive size capacity.
"put" — Update the value of the key if it exists. Otherwise, add the key-value pair. If the number of keys exceeds the capacity, evict the least recently used key.
"get" — Return the value of the key if it exists, otherwise return -1.

Both get and put must run in O(1) average time complexity.

Input:operations = ["LRUCache","put","put","get","put","get","put","get","get","get"], args = [[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]

LRUCache

put

get

put

get

put

get

Output:[null,null,null,1,null,-1,null,-1,3,4]

null

-1

null

-1

Explanation: The cache capacity is 2. After putting keys 1 and 2, getting key 1 returns 1. Putting key 3 evicts key 2 (least recently used). Getting key 2 returns -1 (not found). Putting key 4 evicts key 1. Getting keys 1, 3, and 4 returns -1, 3, and 4 respectively.

Constraints

1 <= capacity <= 3000
0 <= key <= 10^4
0 <= value <= 10^5
At most 2 * 10^5 calls will be made to get and put

Approach

Hash Maps pattern

1. Choose Data Structures

Use a hash map to store key-to-node mappings for O(1) lookup
Use a doubly linked list to maintain the usage order
The head of the list represents the least recently used item
The tail represents the most recently used item

2. Initialize with Sentinel Nodes

Create dummy head and tail nodes that simplify edge cases
Connect them: head.next = tail, tail.prev = head
The actual cache nodes are inserted between these sentinels

3. Implement Get Operation

If the key exists in the map, retrieve the node
Remove the node from its current position in the list
Re-insert it at the end (most recently used position)
Return the node's value
If the key doesn't exist, return -1

4. Implement Put Operation

If the key already exists, remove the old node from the list, update its value, and re-insert at the end
If the key is new and the cache is at capacity, evict the least recently used node (the one right after head)
Create a new node and insert it at the end of the list
Store the key-to-node mapping in the hash map

5. Process All Operations

Iterate through the operations array
Dispatch each operation to the appropriate handler
Collect results: null for constructor and put, the value for get

Key Insight

Combining a hash map with a doubly linked list gives O(1) for both access and ordering
The hash map provides O(1) key lookup; the doubly linked list provides O(1) insertion and removal

Time

O(1) for both get and put

Space

O(capacity) for storing the cache entries

Solution Code

Encode and Decode TinyURL

Copy List with Random Pointer