Skip to main content
Talentd

LFU Cache - Solution & Explanation

HardHash TableLinked ListDesignDoubly-Linked List17 min readAsked at: Amazon, Microsoft, Apple +29
Practice this problem

Problem Statement

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

Implement the LFUCache class:

  • LFUCache(int capacity) Initializes the object with the capacity of the data structure.
  • int get(int key) Gets the value of the key if the key exists in the cache. Otherwise, returns -1.
  • void put(int key, int value) Update the value of the key if present, or inserts the key if not already present. When the cache reaches its capacity, it should invalidate and remove the least frequently used key before inserting a new item. For this problem, when there is a tie (i.e., two or more keys with the same frequency), the least recently used key would be invalidated.

To determine the least frequently used key, a use counter is maintained for each key in the cache. The key with the smallest use counter is the least frequently used key.

When a key is first inserted into the cache, its use counter is set to 1 (due to the put operation). The use counter for a key in the cache is incremented either a get or put operation is called on it.

The functions get and put must each run in O(1) average time complexity.

 

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
// cnt(x) = the use counter for key x
// cache=[] will show the last used order for tiebreakers (leftmost element is  most recent)
LFUCache lfu = new LFUCache(2);
lfu.put(1, 1);   // cache=[1,_], cnt(1)=1
lfu.put(2, 2);   // cache=[2,1], cnt(2)=1, cnt(1)=1
lfu.get(1);      // return 1
                 // cache=[1,2], cnt(2)=1, cnt(1)=2
lfu.put(3, 3);   // 2 is the LFU key because cnt(2)=1 is the smallest, invalidate 2.
                 // cache=[3,1], cnt(3)=1, cnt(1)=2
lfu.get(2);      // return -1 (not found)
lfu.get(3);      // return 3
                 // cache=[3,1], cnt(3)=2, cnt(1)=2
lfu.put(4, 4);   // Both 1 and 3 have the same cnt, but 1 is LRU, invalidate 1.
                 // cache=[4,3], cnt(4)=1, cnt(3)=2
lfu.get(1);      // return -1 (not found)
lfu.get(3);      // return 3
                 // cache=[3,4], cnt(4)=1, cnt(3)=3
lfu.get(4);      // return 4
                 // cache=[4,3], cnt(4)=2, cnt(3)=3

 

Constraints:

  • 1 <= capacity <= 104
  • 0 <= key <= 105
  • 0 <= value <= 109
  • At most 2 * 105 calls will be made to get and put.

 

 

Approach Overview

Problem Overview: Design a cache that evicts the Least Frequently Used (LFU) key when capacity is full. Each operation get(key) and put(key, value) must run in constant time. When multiple keys share the same frequency, the least recently used among them is removed.

Approach 1: HashMap + Frequency Doubly Linked Lists (O(1) time, O(n) space)

The optimal design groups cache entries by their access frequency. Maintain a hash table mapping keys to nodes, and another map from frequency to a doubly linked list that stores nodes with that frequency. Each node stores key, value, and freq. When you call get, look up the node in O(1), remove it from its current frequency list, increment its frequency, and insert it into the next list. Track the current minimum frequency so eviction is constant time: remove the least recently used node from the list representing that frequency. This structure keeps frequency updates and eviction both O(1).

This approach relies on two invariants: (1) nodes are always stored in a list matching their current frequency, and (2) within each frequency list, order represents recency. Because insertion and removal in a linked list are constant time, both cache operations stay O(1). This is the standard interview solution and the one most production-grade LFU implementations follow.

Approach 2: OrderedDict Based LFU (O(1) average time, O(n) space)

Python provides OrderedDict, which maintains insertion order and allows efficient deletion from both ends. You can maintain a dictionary mapping frequencies to OrderedDicts of keys. Another map stores key → (value, frequency). When a key is accessed, remove it from its current OrderedDict, increment its frequency, and insert it into the next one. Eviction happens by removing the first key from the OrderedDict corresponding to the minimum frequency.

This version avoids implementing your own doubly linked list and is easier to code in Python. The tradeoff is less explicit control over the underlying structure, but operations remain O(1) on average because OrderedDict internally uses a hash table and linked list.

Recommended for interviews: Interviewers usually expect the HashMap + frequency doubly linked list design. It demonstrates understanding of system design style data structures, constant-time eviction strategies, and careful state tracking. Mentioning the OrderedDict variation in Python is useful, but implementing the full structure shows deeper mastery.

Approach 1: HashMap and Double Linked List Approach

In this approach, we use a combination of a HashMap (or Dictionary) and a double linked list to ensure O(1) operations for both get and put. The HashMap stores keys and values as well as a reference to the corresponding node in the double linked list, effectively allowing for quick updates and removals. The double linked list maintains the order of keys based on use frequency and recency to guarantee the correct eviction policy.

The Python solution involves two custom classes: Node and DoubleLinkedList. The Node class holds key-value pairs, frequency counts, and pointers to previous and next nodes. The DoubleLinkedList class is used to maintain the order based on frequency and recency of use.

The LFUCache class maintains two dictionaries: node_map which maps keys to nodes, and freq_map which maps frequencies to linked lists. The cache operations (get/put) are implemented to update the frequency of nodes appropriately and handle cache capacity by removing the least frequently and recently used nodes when needed.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(1) for get and put operations due to the use of HashMap and Doubly Linked List.
Space Complexity: O(capacity) due to storage of nodes and frequency mappings.

Try this approach in the editor →

Approach 2: OrderedDict Based Approach

The OrderedDict based approach uses Python's built-in OrderedDict to efficiently track keys while maintaining the insertion order. By managing the dictionary's order, we can track the frequency of access and modify it when performing get or put operations. This may not offer the theoretical O(1) complexity for all operations but is a practical solution with simplicity in Python.

The OrderedDict solution keeps track of keys and their frequencies in separate dictionaries. key_freq_map maps the key to its frequency, while freq_map has OrderedDicts keyed by frequency with keys as their values. This way, we can update both frequency and recency of accesses.

With the built-in nature of Python's OrderedDict, the implementation remains concise and takes advantage of existing functionality to manage ordering effectively, even if all operations might not run in strict O(1) time.

Code

Python

Python

Complexity

Time Complexity: Average O(1) for both get and put, due to the effectiveness of OrderedDict for these operations.
Space Complexity: O(capacity) for storing nodes and their frequency mappings.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoRust

Python

Java

C++

Go

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
HashMap and Double Linked List Approach

Time Complexity: O(1) for get and put operations due to the use of HashMap and Doubly Linked List.
Space Complexity: O(capacity) due to storage of nodes and frequency mappings.

OrderedDict Based Approach

Time Complexity: Average O(1) for both get and put, due to the effectiveness of OrderedDict for these operations.
Space Complexity: O(capacity) for storing nodes and their frequency mappings.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
HashMap + Frequency Doubly Linked ListsO(1) for get and putO(n)Standard optimal solution for LFU cache design problems and interviews
Frequency Map + OrderedDict (Python)O(1) averageO(n)Python implementations where built-in ordered dictionaries simplify LRU handling
Naive Frequency TrackingO(n) evictionO(n)Conceptual baseline; scan keys to find the least frequently used item

Video Solution

Imlement LFU Cache | Leetcode(Hard) • take U forward • 217,756 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is LFU Cache easy or hard?
LFU Cache is classified as a hard problem because it requires designing multiple interacting data structures. The challenge is maintaining both frequency counts and recency order while guaranteeing O(1) operations for get and put.
How to solve LFU Cache in O(1)?
Use two hash maps and frequency-linked lists. One map stores key → node for direct access, and another maps frequency → doubly linked list of nodes with that frequency. On every access, remove the node from its current list, increase its frequency, and insert it into the next list. Eviction removes the least recently used node from the minimum-frequency list.
LFU Cache Python or Java solution
Python solutions often use dictionaries and OrderedDict to track frequency buckets efficiently. Java implementations typically combine HashMap with custom doubly linked list nodes to maintain constant-time insertion and removal. Both approaches implement O(1) get and put operations.
What is the best approach for LFU Cache?
The best approach uses a hash map combined with frequency-based doubly linked lists. A map provides O(1) access to nodes, while lists grouped by frequency maintain recency order for ties. Tracking the minimum frequency allows constant-time eviction. This design keeps both get and put operations O(1).
Is LFU Cache asked at Google Amazon Meta?
LFU Cache is a common hard-level system design style data structure problem. Variants have appeared in interviews at companies such as Google, Amazon, Meta, and Microsoft because it tests hash maps, linked lists, and constant-time data structure design.
What data structure is used in LFU Cache?
The standard implementation uses a hash table combined with doubly linked lists grouped by frequency. The hash map provides O(1) key lookup, while each doubly linked list maintains recency order among keys with the same frequency. Some Python solutions replace custom lists with OrderedDict.
What is the time complexity of LFU Cache?
The optimal LFU cache implementation runs get and put operations in O(1) time. This is achieved using a hash table for key lookups and doubly linked lists to maintain ordering within each frequency bucket. Space complexity is O(n) because every cached key must be stored along with frequency metadata.

Ready to solve this problem?

Practice LFU Cache with our built-in code editor and test cases.

Practice on FleetCode
Previous

Design In-Memory File System

Next

LRU Cache