LRU Cache

Solution Approach

Was this helpful?

Medium•data-structure•Expected: O(1) time, O(n) space

hash-maplinked-list

Problem

Design a Least Recently Used cache supporting get and put operations in O(1) time.

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: Cache capacity=2. When put(3,3) is called, key 2 is evicted (least recently used).
             When put(4,4) is called, key 1 is evicted.

Reference solution unlocks after your first submission

Language: