mafeshsho8lmafeshsho8l
Get Started
All coding questions

LRU Cache

medium
LeetCode Top 100NeetCode 150designhashinglinked-list

Problem

Design a cache with a fixed capacity that supports get and put in constant time. When the cache is full and a new key is added, evict the least recently used entry. Reading or updating a key marks it most recently used.

Examples

Input: capacity 2; put(1,1), put(2,2), get(1), put(3,3), get(2)
Output: get(1)=1, get(2)=-1
Adding key 3 evicts the least recently used key 2.

Constraints

  • • 1 <= capacity <= 3000
  • • At most 2 * 10^5 calls to get and put
Hints(tap to reveal)
  • 1. A hash map gives O(1) lookup.
  • 2. A doubly linked list maintains recency order for O(1) eviction.
Optimal approach(spoiler)
  1. Pair a hash map from key to node with a doubly linked list ordered by recency.
  2. On access, unlink the node and move it to the most-recent end.
  3. On insert past capacity, evict the node at the least-recent end.
  4. The map gives O(1) lookup; list splicing gives O(1) reordering.
  5. Both operations run in O(1) time.

Ready to solve it?

Write your solution in the editor and get an instant AI grade on correctness, edge cases, and complexity.

Practice in the editor