LRU Cache

Medium · hash map

A cache remembers at most capacity key and value pairs. It starts empty and receives a list of operations. operations[i] is either "get" or "put", and args[i] holds its arguments: [key] for a "get" and [key, value] for a "put".

"get" returns the value stored for key, or -1 if the key is not in the cache.
"put" stores value for key. If the key is already in the cache its value is replaced. If it is a new key and the cache already holds capacity pairs, first remove the pair that was least recently used.

A pair counts as used whenever it is read by a "get" that finds it, or written by a "put" (including a "put" that only replaces the value). A "get" for a missing key changes nothing.

Return a list with the result of every "get", in the order they appear.

Examples

Example 1

Input: capacity = 2, operations = ["put", "put", "get", "put", "get", "get"], args = [[1, 10], [2, 20], [1], [3, 30], [2], [3]]

Output: [10, -1, 30]

Reading key 1 makes key 2 the least recently used, so putting key 3 removes key 2.

Example 2

Input: capacity = 1, operations = ["put", "put", "get", "get"], args = [[1, 1], [2, 2], [1], [2]]

Output: [-1, 2]

The cache holds one pair, so putting key 2 removes key 1.

Example 3

Input: capacity = 2, operations = ["put", "put", "put", "put", "get", "get", "get"], args = [[1, 1], [2, 2], [1, 100], [3, 3], [1], [2], [3]]

Output: [100, -1, 3]

Replacing the value of key 1 counts as using it, so key 2 is the one removed when key 3 arrives.

Constraints

1 <= capacity <= 3000
1 <= len(operations) <= 10^4
len(args) == len(operations)
operations[i] is get or put
0 <= key <= 10^5
0 <= value <= 10^9