66. LRU Cache

PRO

Medium

Topics

Helpful tools to learn & understand

Visualize LogicActive Simulator

Watch key transitions, pointers, and variables update step-by-step.

Open

Check Solutions

Read clean, documented implementations across multiple patterns.

View Code

Thinkpad (Draw & Note)

Sketch diagrams on an infinite canvas and draft notes directly inline.

Draw

Example 1:

Input:

capacity = 2, operations = ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] with values [[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: LRUCache lRUCache = new LRUCache(2); lRUCache.put(1, 1); // cache is {1=1} lRUCache.put(2, 2); // cache is {1=1, 2=2} lRUCache.get(1); // return 1 lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3} lRUCache.get(2); // returns -1 (not found) lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3} lRUCache.get(1); // return -1 (not found) lRUCache.get(3); // return 3 lRUCache.get(4); // return 4

Constraints:

•
•
•
•

Time Complexity

O(1)

Space Complexity

O(capacity)