Least Frequently Used (LFU) Cache - Design and Implementation
On how LFU works and how to implement an optimal solution.
What is LFU Cache?
The basic principle of LFU caching is to remove the least frequently used items first when the cache reaches its capacity limit. This means that the cache keeps track of the frequency with which each item is accessed, and when it needs to make space for a new item, it removes the item that has been accessed the least frequently.
LFU Cache Design
To implement a Least Frequently Used (LFU) cache solution we need to design a data structure that would support the following operations:
LFUCache(int capacity)
- initialises the object with the capacity of the data structure.int get(int key)
- gets the value of thekey
if thekey
exists in the cache. Otherwise, returns-1
.void put(int key, int value)
- updates the value of thekey
if present, or inserts thekey
if not already present. When the cache reaches itscapacity
, 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 usedkey
would be invalidated.
The frequency for a key
is incremented whenever a get
or a put
operation is called on the element.
Let’s run through an example to better understand how this would work:
Let’s say we have a cache with a capacity of 2
LFU(2)
and we callput(1,1)
→ Our LFU will become{1,1,1}
as we add thekey 1
withvalue 1
which currently has afrequency of 1
Then we call
put(2,2)
→ Our LFU will become{2,2,1},{1,1,1}
. We added a new element withkey 2
andvalue 2
which currently has afrequency of 1
. Since elements with key 1 and 2 have the same frequency of 1, we add the most recently used element (the one with key 2) to the front of the list.Then we call
get(1)
. Our LFU will return 1 and the new LFU will be{1,1,2}, {2,2,1}
. This is because we increase the frequency of element with key 2 to 2 (due to the read operation) and we move it to the front of the list because it has higher frequency than the other element.Then we call
put(3, 3)
. Our LFU will become{1,1,2}, {3,3,1}
. A new element comes in but our cache is at full capacity so we need to remove an element. We remove from the end of the list (as this is where the element with the least frequency and least recency is stored), so{2,2,1}
gets removed. We then add the new element with a frequency of 1,{3,3,1}
.We call
get(2)
. We return-1
as the element no longer exists in the cache.We call
get(3)
. We return3
and the LFU becomes{3,3,2}, {1,1,2}
. We increase the frequency of 3 and move it before key 1 as even though they have the same frequency, key 3 has been accessed more recently.We call
put(4,4)
. The LFU becomes{3,3,2}, {4,4,1}
. New element comes in, cache is full, we remove the last element with key 1 and add the new element with key 4.We call
get(1)
. We return-1
as element is no longer present in the cache.We call
get(3)
. We return3
and our LFU becomes{3,3,3}, {4,4,1}
. The read operation increases the frequency of element at key 3 to 3.We call
get(4)
. We return4
and our LFU becomes{3,3,3}, {4,4,2}
.
Possible Implementations
Using a brute force approach, we could have an array with the size of the cache. Each element in the array would store the item along with its frequency and last access time. When we get an element, we’d have to iterate through the array to find our element and update the item with the incremented frequency value. This means getting an element would be on average O(n). To put an item when the cache is full, we’d have to look for an item to evict. So we’ll iterate through the whole array and look for the item with the least frequency and oldest access time. This would take O(n).
Using a min-heap data structure would be an improvement - each node will hold the cached element along with its frequency. This makes it easy to remove an element when the cache is full as the least recently and frequently used element will be a the top. The problem comes when inserting or reading from the cache, as any operation will mean the min-heap will need to be rebalanced which will take O(logn).
Solution in constant time
To implement an LFU that uses constant time for pushing and getting items, we’re going to need 2 data structures: a key map and a frequency map.
Key Map - stores the key of the item and the item node containing the key, value and frequency.

Frequency Map - stores the frequency as key and a doubly linked list of all the cached items having that frequency as value. The items in the doubly linked list are sorted by recency such that most recently accessed items will be at the head of the list and the least recently used at the tail. Due to the nature of the doubly linked list, removing, adding and updating a cached item will take O(1).

Given those two data structures, the cache operations would have the following logic:
get
operation for an item X:check that X is in our key map. If it doesn’t exist return -1. Otherwise get the frequency from the value node.
for the frequency we’ve obtained above, get the doubly linked list from the frequency map. Delete the node from the doubly linked list. Create a new node with the incremented frequency and added it to the frequency map at the head of the doubly linked list.
Following the above instructions, the implementation for theget
operation should look similar to this:

put
operation for an item X:if the item already exists in the cache, it returns the node and updates the frequency (hence, we call
getNode
which does all of these)if the item doesn’t exist in the cache:
if the cache is full - we remove the least recently and frequency used item, which should be the tail of the doubly linked list value in the frequency map with the minimum frequency.
then we add the item at the head of the doubly linked list with has the frequency of
1
Considering the above, the implementation for the put operation would look like:

Putting everything together, the code should look like this.
Conclusion
In this article we had a look on how we would go about implementing an LFU.
To learn more about caching, have a look at the following articles:
Or stay tuned as in the upcoming articles, we'll dive deeper into:
Types of Caches: Exploring different caching mechanisms like in-memory, distributed, and CDN caching.
Deployment Strategies: Understanding how to integrate caching into your architecture.
Metrics: How to monitor cache performance for optimal results.
Implementation Solutions: Practical examples with popular caching tools and libraries.