Coding Interview PatternsLFU Cache
HardCustom Data Structures

LFU Cache

Explanation & Solution

Practice Problem

Description

Design and implement a data structure for a Least Frequently Used (LFU) cache.

Implement a function that processes an array of operations and an array of arguments:

  • "LFUCache" — Initializes the LFU cache with capacity.
  • "put" — Update the value of key if it exists, otherwise insert. When capacity is reached, evict the least frequently used key. If multiple keys have the same frequency, evict the least recently used among them.
  • "get" — Return the value of key if it exists, otherwise return -1. Accessing a key increases its frequency by 1.

Both get and put must run in O(1) average time complexity.

Input:operations = ["LFUCache","put","put","get","put","get","get","put","get","get","get"], args = [[2],[1,1],[2,2],[1],[3,3],[2],[3],[4,4],[1],[3],[4]]
0
LFUCache
1
put
2
put
3
get
4
put
5
get
6
get
7
put
8
get
9
get
10
get
Output:[null,null,null,1,null,-1,3,null,-1,3,4]
0
null
1
null
2
null
3
1
4
null
5
-1
6
3
7
null
8
-1
9
3
10
4

Explanation: Capacity 2. put(1,1), put(2,2). get(1)=1 (freq[1]=2). put(3,3): evict key 2 (LFU, freq=1). get(2)=-1. get(3)=3. put(4,4): evict key 3 (LFU freq=1, but 3 was used more recently... wait — 3 was just accessed above. freq[3]=2, freq[1]=2. Evict the LRU among freq=2: key 1 (accessed earlier). So get(1)=-1, get(3)=3, get(4)=4.

Constraints

  • 1 <= capacity <= 10^4
  • 0 <= key <= 10^5
  • 0 <= value <= 10^9
  • At most 2 * 10^5 calls to get and put

Approach

Custom Data Structures pattern

1. Three Maps + minFreq

  • keyVal: key → value
  • keyFreq: key → current access frequency
  • freqKeys: frequency → insertion-ordered Map of keys (Map preserves insertion order for LRU tiebreaking)
  • minFreq: tracks the minimum frequency for O(1) eviction

2. IncrementFreq Helper

  • Increase the key's frequency by 1 in keyFreq
  • Remove the key from freqKeys[oldFreq]
  • If that bucket is now empty and oldFreq === minFreq, increment minFreq
  • Add the key to freqKeys[newFreq]

3. Implement Get

  • If key doesn't exist, return -1
  • Otherwise, call incrementFreq, then return the value

4. Implement Put

  • If key exists: update value, call incrementFreq
  • If new key:
  • If at capacity, evict: get the first key from freqKeys[minFreq] (LRU among LFU) and remove it from all maps
  • Insert the new key with frequency 1
  • Reset minFreq = 1

5. LRU Tiebreaking with Ordered Map

  • Using a Map (which preserves insertion order) for freqKeys[freq] gives O(1) access to the least recently used key at any frequency
  • The first entry (keys().next().value) is always the LRU at that frequency

Key Insight

  • Three maps + minFreq achieves O(1) for all operations
  • The nested Map structure handles both frequency ordering and LRU tiebreaking simultaneously
Time
O(1) average for get and put
Space
O(capacity)

Solution Code

Previous
Maximum Frequency Stack
Next
All O(1) Data Structure