What is the time complexity of LFU Cache?

The optimal solution has a time complexity of O(1).

What is the space complexity of LFU Cache?

The space complexity is O(capacity).

What data structures are used to solve LFU Cache?

This problem uses Hash Table, Linked List, Design, Doubly-Linked List. Understanding these concepts is essential for solving this Hard problem efficiently.

What are the key insights for solving LFU Cache?

Insight 1: We need to keep track of the frequency of each key and the order in which keys with the same frequency were accessed. Insight 2: Using a combination of HashMaps and Doubly Linked Lists (or OrderedDict in Python) allows for O(1) average time complexity for both `get` and `put` operations.

Which companies ask LeetCode 460. LFU Cache in interviews?

This problem is frequently asked at Citadel, Coupang, DoorDash, Gameskraft, KLA and 8 more companies.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

LFU Cache - LeetCode 460 Solution

LFU Cache - Complete Solution Guide

LFU Cache is LeetCode problem 460, a Hard level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

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 us

Detailed Explanation

The problem asks us to design and implement a Least Frequently Used (LFU) cache with a given capacity. The cache should support two operations: `get(key)` and `put(key, value)`. `get(key)` retrieves the value associated with the key if it exists; otherwise, it returns -1. `put(key, value)` either updates the value if the key exists or inserts a new key-value pair. When the cache is full, the least frequently used key should be evicted. If there is a tie in frequency, the least recently used key should be evicted. A use counter is maintained for each key. When the cache is initialized, the use counter is 1. When a key is accessed via `get` or `put`, its counter increments.

Solution Approach

The solution uses three main data structures: `key_to_val` (a HashMap to store key-value pairs), `key_to_freq` (a HashMap to store the frequency of each key), and `freq_to_keys` (a HashMap where keys are frequencies, and values are OrderedDicts or LinkedHashSets representing the keys with that frequency). The `min_freq` variable tracks the minimum frequency in the cache. The `get` operation retrieves the value, increments the key's frequency, and moves the key to the corresponding frequency list. The `put` operation updates the value if the key exists, otherwise, if the cache is full, the least frequently and least recently used key is evicted, and the new key-value pair is inserted with frequency 1.

Step-by-Step Algorithm

Step 1: **Initialization:** Create the necessary HashMaps and the `min_freq` variable.
Step 2: **`get(key)`:** a. Check if the key exists in `key_to_val`. If not, return -1. b. Get the current frequency of the key from `key_to_freq`. c. Remove the key from the OrderedDict associated with the current frequency in `freq_to_keys`. d. If the OrderedDict for the current frequency is now empty and the current frequency is equal to `min_freq`, increment `min_freq`. e. Increment the frequency of the key in `key_to_freq`. f. Add the key to the OrderedDict associated with the new frequency in `freq_to_keys`. g. Return the value from `key_to_val`.
Step 3: **`put(key, value)`:** a. If the cache capacity is 0, return. b. If the key exists in `key_to_val`, update the value and call `get(key)` to update frequency and move it to correct frequency bucket. c. If the cache is full, remove the least frequently and least recently used key: i. Get the least frequently used key from the head of the OrderedDict associated with `min_freq` in `freq_to_keys`. ii. Remove the key from `key_to_val` and `key_to_freq`. d. Insert the new key-value pair: i. Add the key-value pair to `key_to_val`. ii. Set the frequency of the key to 1 in `key_to_freq`. iii. Add the key to the OrderedDict associated with frequency 1 in `freq_to_keys`. iv. Set `min_freq` to 1.

Key Insights

Insight 1: We need to keep track of the frequency of each key and the order in which keys with the same frequency were accessed.
Insight 2: Using a combination of HashMaps and Doubly Linked Lists (or OrderedDict in Python) allows for O(1) average time complexity for both `get` and `put` operations.
Insight 3: Maintaining a `min_freq` variable is crucial for efficiently identifying the least frequently used keys for eviction.

Complexity Analysis

Time Complexity: O(1)

Space Complexity: O(capacity)

Topics

This problem involves: Hash Table, Linked List, Design, Doubly-Linked List.

Companies

Asked at: Citadel, Coupang, DoorDash, Gameskraft, KLA, PayPal, Rippling, Salesforce, ServiceNow, Siemens, Visa, Walmart Labs, Zomato.

LFU Cache | LeetCode 460

Hard

Hash Table Linked List Design Doubly-Linked List

Time: O(1)Space: O(capacity)

Solution Code

Available in:

import java.util.HashMap;
import java.util.LinkedHashSet;

class LFUCache {

    private int capacity;
    private HashMap<Integer, Integer> keyToVal;
    private HashMap<Integer, Integer> keyToFreq;
    private HashMap<Integer, LinkedHashSet<Integer>> freqToKeys;
    private int minFreq;

    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.keyToVal = new HashMap<>();
        this.keyToFreq = new HashMap<>();
        this.freqToKeys = new HashMap<>();
        this.minFreq = 0;
    }

    public int get(int key) {
        if (!keyToVal.containsKey(key)) {
            return -1;
        }

        int freq = keyToFreq.get(key);
        freqToKeys.get(freq).remove(key);

        if (freqToKeys.get(freq).isEmpty()) {
            if (freq == minFreq) {
                minFreq++;
            }
        }

        int newFreq = freq + 1;
        keyToFreq.put(key, newFreq);
        freqToKeys.computeIfAbsent(newFreq, k -> new LinkedHashSet<>()).add(key);

        return keyToVal.get(key);
    }

    public void put(int key, int value) {
        if (capacity <= 0) {
            return;
        }

        if (keyToVal.containsKey(key)) {
            keyToVal.put(key, value);
            get(key);
            return;
        }

        if (keyToVal.size() >= capacity) {
            int lfuLruKey = freqToKeys.get(minFreq).iterator().next();
            freqToKeys.get(minFreq).remove(lfuLruKey);
            keyToVal.remove(lfuLruKey);
            keyToFreq.remove(lfuLruKey);
        }

        keyToVal.put(key, value);
        keyToFreq.put(key, 1);
        freqToKeys.computeIfAbsent(1, k -> new LinkedHashSet<>()).add(key);
        minFreq = 1;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 460: LFU Cache - Detailed explanation and solution approaches.

Topics

Hash Table Linked List Design Doubly-Linked List

Companies

CitadelCoupangDoorDashGameskraftKLAPayPalRipplingSalesforce

Stats

Difficulty:Hard

Languages:4

Companies:13

Problem #:460

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

3 steps

1
Step 1: **Initialization:** Create the necessary HashMaps and the `min_freq` variable.
2
Step 2: **`get(key)`:** a. Check if the key exists in `key_to_val`. If not, return -1. b. Get the current frequency of the key from `key_to_freq`. c. Remove the key from the OrderedDict associated with the current frequency in `freq_to_keys`. d. If the OrderedDict for the current frequency is now empty and the current frequency is equal to `min_freq`, increment `min_freq`. e. Increment the frequency of the key in `key_to_freq`. f. Add the key to the OrderedDict associated with the new frequency in `freq_to_keys`. g. Return the value from `key_to_val`.
3
Step 3: **`put(key, value)`:** a. If the cache capacity is 0, return. b. If the key exists in `key_to_val`, update the value and call `get(key)` to update frequency and move it to correct frequency bucket. c. If the cache is full, remove the least frequently and least recently used key: i. Get the least frequently used key from the head of the OrderedDict associated with `min_freq` in `freq_to_keys`. ii. Remove the key from `key_to_val` and `key_to_freq`. d. Insert the new key-value pair: i. Add the key-value pair to `key_to_val`. ii. Set the frequency of the key to 1 in `key_to_freq`. iii. Add the key to the OrderedDict associated with frequency 1 in `freq_to_keys`. iv. Set `min_freq` to 1.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(1)

⚡ Constant time - Super fast! Same speed regardless of input size.

💾

Space Complexity

O(capacity)

📝

Why?

The HashMap lookups and insertions are O(1) on average. Removing and adding elements from/to the head/tail of the doubly linked list (or using OrderedDictionary's popitem(last=False) method, or LinkedHashSet's iterator) is also O(1). The space is bounded by the capacity of the cache since we store, at most, `capacity` number of key-value pairs.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Using a Single Doubly Linked List and a HashMap

This approach maintains a single doubly linked list to represent the order of access. Each node contains the key, value, and frequency. The HashMap maps keys to nodes in the list. When a key is accessed, the node is moved to the tail of the list, and its frequency is incremented. When the cache is full, nodes are evicted from the head of the list based on the frequency and LRU order.

Time: O(n) for eviction in the worst-case (if needing to traverse through same-frequency entries). O(1) for get/put if key is present.Space: O(capacity)

Trade-offs: This approach is simpler to implement but has a potentially worse time complexity for eviction in some cases. It is less efficient overall.

✨

Key Insights

1Insight 1: We need to keep track of the frequency of each key and the order in which keys with the same frequency were accessed.
2Insight 2: Using a combination of HashMaps and Doubly Linked Lists (or OrderedDict in Python) allows for O(1) average time complexity for both `get` and `put` operations.
3Insight 3: Maintaining a `min_freq` variable is crucial for efficiently identifying the least frequently used keys for eviction.

📚

Key Terms Explained

For Students

Hash Table

A data structure that maps keys to values for quick lookup. Like a dictionary!

Linked List

Elements connected via pointers. Like a chain where each link knows the next.

Edge Cases

Edge case 1: **Capacity is 0.** The code should handle the case where the capacity of the cache is 0 by simply returning without doing anything in the `put` method. The Java and C++ implementations handle it by immediately returning, and Python also handles correctly.
Edge case 2: **Key already exists in the cache.** The code must update the key's value, increment its frequency, and move it to the appropriate frequency list. The `get` method implicitly handles promoting existing keys by bumping their frequency.
Edge case 3: **When cache is full, evicting the *least* frequently used item.** It is crucial to update the `min_freq` whenever an item is evicted or its frequency is incremented. If the frequency bucket associated with `min_freq` becomes empty after a get operation, `min_freq` must be updated.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: **Not updating the `min_freq` correctly.** Failing to update `min_freq` after evicting the least frequently used key or when its frequency is incremented can lead to incorrect eviction decisions.

✗Common mistake 2: **Incorrectly handling the LRU order within a frequency list.** Using a standard HashMap to store keys with the same frequency will not preserve the LRU order. An OrderedDict (Python) or LinkedHashSet (Java) or other ordered data structures must be used.

✗Common mistake 3: Forgetting the edge case when the capacity is zero.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: **Web browser caching.** LFU caches can be used to store frequently accessed web pages, improving browsing speed.

🏦Real-world scenario 2: **Database caching.** Databases can use LFU caches to store frequently queried data, reducing the load on the database server.

🎮Real-world scenario 3: **Content Delivery Networks (CDNs).** CDNs utilize LFU caching to store popular content closer to users, improving content delivery performance.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

Hash tables trade space for time. Before using one, consider if the problem constraints allow the extra memory. In interviews, always mention this trade-off.

🎯 Interview Tip

It's okay to not finish hard problems in interviews. Show your problem-solving process.

⚠️ Watch Out

Don't forget to handle key collisions and null/undefined keys. Consider what happens with duplicate values.

👨‍💻 From Experience

I encountered a variation of this problem in a system design interview. The key was recognizing the underlying pattern.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: September 9, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 13

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 6

❓

Frequently Asked Questions

What are the trade-offs of using a hash table?

Hash tables provide O(1) average-case lookup, insertion, and deletion, making them ideal for frequency counting and duplicate detection. However, they use O(n) extra space and may degrade to O(n) time in worst-case scenarios with hash collisions. Always consider if the space trade-off is acceptable.

Why use a dummy node in linked list problems?

A dummy node simplifies edge cases where the head might change (insertion/deletion at head) or when building a new list. Initialize dummy.next = head, work with dummy.next throughout, and return dummy.next at the end to handle all cases uniformly.

How do I approach hard algorithm problems?

Hard problems often require: 1) Breaking down into subproblems, 2) Combining multiple advanced techniques, 3) Careful optimization of brute force. Start with a working solution (even O(n²) or worse), then optimize. Draw examples, identify patterns, and think about what makes this problem unique.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "LFU Cache"?

For this hard-level Hash Table problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether linked list techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?