LFU Cache

hard

data-structureTime: O(1)Space: O(n)Frequency: 3

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).

hash-map

Shortcuts

SubmitCtrl↵
Toggle commentCtrl/
Find in codeCtrlF
UndoCtrlZ
Exit fullscreenEsc

Interview tips

→Aim for O(1) time and O(n) space.
→Walk through your approach with a small example first.
→Handle edge cases: empty input, single element, overflow.
→Code is auto-saved as you type — refresh-safe.

data-structureTime: O(1)Space: O(n)Frequency: 3

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).

hash-map