LFU Cache

Solution Approach

Was this helpful?

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

hash-map

Problem

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

Example 1:

Input: ["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
       [[2], [1,1], [2,2], [1], [3,3], [2], [3], [4,4], [1], [3], [4]]
Output: [null, null, null, 1, null, -1, 3, null, -1, 3, 4]
Explanation: Cache capacity=2. After put(3,3), key 2 is evicted (least frequent).
             After put(4,4), key 1 is evicted (least frequent).

Reference solution unlocks after your first submission

Language: