What is the time complexity of LRU Cache?

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

What data structures are used to solve LRU Cache?

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

What are the key insights for solving LRU Cache?

Insight 1: Using a hash table (unordered map, dictionary) allows O(1) average-case time complexity for `get` and `put` operations because we can quickly check if a key exists. Insight 2: A doubly-linked list (or an ordered dictionary like OrderedDict in Python or LinkedHashMap in Java) is used to keep track of the order in which keys were accessed. Moving a key to the tail (or end) of the list on every `get` and `put` operation ensures that the head (or beginning) of the list always contains the least recently used key.

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

LRU Cache - LeetCode 146 Solution

Q: Which companies ask LeetCode 146. LRU Cache in interviews?

This problem is frequently asked at AppFolio, Arista Networks, Aurora, Autodesk, BP and 96 more companies.

LRU Cache - Complete Solution Guide

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

Problem Statement

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache . Implement the LRUCache class: LRUCache(int capacity) Initialize the LRU cache with positive size capacity . int get(int key) Return the value of the key if the key exists, otherwise return -1 . void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently u

Detailed Explanation

The problem requires designing and implementing an LRU (Least Recently Used) cache. An LRU cache is a data structure that stores key-value pairs and has a limited capacity. When the cache is full and a new key-value pair needs to be added, the least recently used item is evicted to make space. The `get` operation should return the value associated with a given key if it exists in the cache, otherwise return -1. The `put` operation should update the value of a key if it exists, or add a new key-value pair to the cache. Both `get` and `put` operations must have an average time complexity of O(1). The capacity of the cache is initialized during the creation of the `LRUCache` object.

Solution Approach

The solution uses a hash table (dictionary/unordered map) and a doubly-linked list (or similar ordered structure) to implement the LRU cache. The hash table stores key-value pairs, where the key is the cache key, and the value is the corresponding value or a pointer to the node in the linked list. The linked list maintains the order of keys based on their usage. The most recently used key is at the tail of the list, and the least recently used key is at the head. When a key is accessed (either through `get` or `put`), it's moved to the tail of the linked list. When a new key is added and the cache is full, the key at the head of the linked list is removed (LRU eviction).

Step-by-Step Algorithm

Step 1: Initialize the LRUCache with a capacity and create a hash table and a doubly-linked list (or equivalent ordered structure).
Step 2: Implement the `get` operation: If the key exists in the hash table, move the corresponding node to the end of the linked list and return the value. Otherwise, return -1.
Step 3: Implement the `put` operation: If the key exists in the hash table, update the value and move the node to the end of the linked list. If the key doesn't exist, create a new node and add it to the end of the linked list. If the cache is full, remove the node at the head of the linked list and its corresponding entry in the hash table before adding the new node.
Step 4: Maintain the doubly-linked list to reflect access order. Every time get or put is called, move the accessed node to the tail of the linked list. If the cache exceeds capacity during a put operation, remove the head node.
Step 5: Ensure that the hash table and the linked list are synchronized. When a node is removed from the linked list, it should also be removed from the hash table, and vice versa.

Key Insights

Insight 1: Using a hash table (unordered map, dictionary) allows O(1) average-case time complexity for `get` and `put` operations because we can quickly check if a key exists.
Insight 2: A doubly-linked list (or an ordered dictionary like OrderedDict in Python or LinkedHashMap in Java) is used to keep track of the order in which keys were accessed. Moving a key to the tail (or end) of the list on every `get` and `put` operation ensures that the head (or beginning) of the list always contains the least recently used key.
Insight 3: When `put` is called and the cache is full, the node at the head of the linked list (the LRU element) must be removed from both the linked list and the hash table to maintain O(1) complexity.

Complexity Analysis

Time Complexity: O(1)

Space Complexity: O(n)

Topics

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

Companies

Asked at: AppFolio, Arista Networks, Aurora, Autodesk, BP, BitGo, Booking.com, ByteDance, Capital One, Chewy, Cisco, Citadel, Citrix, Cloudflare, Cohesity, Confluent, Coupang, Cruise, Disney, Docusign, DoorDash, Expedia, Fiverr, Freecharge, FreshWorks, General Motors, Goldman Sachs, Grab, Groww, Highspot, IBM, Intel, Intuit, J.P. Morgan, KLA, LinkedIn, Media.net, Mobileye, MongoDB, Morgan Stanley, Myntra, Navan, NetApp, Netflix, Niantic, Nokia, Nordstrom, Nutanix, Nvidia, Okta, Optiver, Oracle, Palantir Technologies, Palo Alto Networks, PayPal, PhonePe, Qualcomm, Rakuten, Reddit, Ripple, Rivian, Roku, Rubrik, SAP, Salesforce, Samsung, ServiceNow, Shopee, Shopify, Snap, Snowflake, SoFi, Splunk, Sprinklr, Squarespace, Swiggy, Tencent, Tesla, The Trade Desk, ThousandEyes, TikTok, Tripadvisor, Turo, Twitch, VMware, Verkada, Vimeo, Visa, Walmart Labs, Workday, X, Yahoo, Yandex, ZScaler, Zalando, Zenefits, Zepto, eBay, razorpay, smartnews, thoughtspot.

LRU Cache | LeetCode 146

Medium

Hash Table Linked List Design Doubly-Linked List

Time: O(1)Space: O(n)

Solution Code

Available in:

import java.util.LinkedHashMap;
import java.util.Map;

class LRUCache {

    private int capacity;
    private LinkedHashMap<Integer, Integer> cache;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
                return size() > capacity;
            }
        };
    }
    
    public int get(int key) {
        if (!cache.containsKey(key)) {
            return -1;
        }
        
        return cache.get(key);
    }
    
    public void put(int key, int value) {
        cache.put(key, value);
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 146: LRU Cache - Detailed explanation and solution approaches.

Topics

Hash Table Linked List Design Doubly-Linked List

Companies

AppFolioArista NetworksAuroraAutodeskBPBitGoBooking.comByteDance

Stats

Difficulty:Medium

Languages:4

Companies:101

Problem #:146

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

5 steps

1
Step 1: Initialize the LRUCache with a capacity and create a hash table and a doubly-linked list (or equivalent ordered structure).
2
Step 2: Implement the `get` operation: If the key exists in the hash table, move the corresponding node to the end of the linked list and return the value. Otherwise, return -1.
3
Step 3: Implement the `put` operation: If the key exists in the hash table, update the value and move the node to the end of the linked list. If the key doesn't exist, create a new node and add it to the end of the linked list. If the cache is full, remove the node at the head of the linked list and its corresponding entry in the hash table before adding the new node.
4
Step 4: Maintain the doubly-linked list to reflect access order. Every time get or put is called, move the accessed node to the tail of the linked list. If the cache exceeds capacity during a put operation, remove the head node.
5
Step 5: Ensure that the hash table and the linked list are synchronized. When a node is removed from the linked list, it should also be removed from the hash table, and vice versa.

💡

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(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The hash table allows for O(1) average-case retrieval of a node given its key. The doubly-linked list allows for O(1) addition and removal of nodes at both ends. Since `get` involves a hash table lookup and potentially moving the node in the list, it takes O(1) on average. `put` involves a hash table lookup, potential addition to the list, potential removal from the list, and potential addition to the hash table. All of these operations take O(1) on average.

📖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 LinkedHashMap (Java)

Java's LinkedHashMap provides built-in support for LRU caches by setting the `accessOrder` flag to true in the constructor. The `removeEldestEntry` method can be overridden to automatically remove the eldest entry when the capacity is exceeded.

Time: O(1) for both `get` and `put` operations on average.Space: O(n), where n is the capacity of the cache.

Trade-offs: This approach is simpler to implement in Java because it leverages the built-in functionality of the `LinkedHashMap`. It's generally preferred in Java unless there's a specific need for a custom implementation.

✨

Key Insights

1Insight 1: Using a hash table (unordered map, dictionary) allows O(1) average-case time complexity for `get` and `put` operations because we can quickly check if a key exists.
2Insight 2: A doubly-linked list (or an ordered dictionary like OrderedDict in Python or LinkedHashMap in Java) is used to keep track of the order in which keys were accessed. Moving a key to the tail (or end) of the list on every `get` and `put` operation ensures that the head (or beginning) of the list always contains the least recently used key.
3Insight 3: When `put` is called and the cache is full, the node at the head of the linked list (the LRU element) must be removed from both the linked list and the hash table to maintain O(1) complexity.

📚

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: Empty cache (initial state). The `get` operation should return -1 for any key.
Edge case 2: Cache is full and a new element needs to be inserted. The LRU element should be evicted correctly.
Edge case 3: Inserting an existing key should update the value and move the key to the most recently used position.
Edge case 4: Capacity is 1. Should still function correctly, alternating between the single allowed key and evicting it.
Edge case 5: Inserting the same key multiple times consecutively doesn't result in incorrect ordering.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Forgetting to update the hash table when removing a node from the linked list. This can lead to incorrect values being returned or memory leaks.

✗Common mistake 2: Not handling the case where a key already exists in the cache when calling `put`. The value should be updated, and the key should be moved to the end of the linked list.

✗Common mistake 3: Failing to move the accessed node to the end of the list during the `get` operation. This will result in incorrect LRU eviction.

✗Common mistake 4: Incorrectly implementing the doubly linked list operations (add to head, remove node). Off-by-one errors can lead to crashes and incorrect behavior.

✅

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 browsers use LRU caches to store frequently accessed web pages, images, and other resources. This allows the browser to quickly retrieve these resources without having to download them again from the server.

🏦Real-world scenario 2: Databases use LRU caches to store frequently accessed data blocks. This can significantly improve the performance of database queries by reducing the number of disk I/O operations.

🎮Real-world scenario 3: Operating systems use LRU caches to manage memory pages. When the system runs out of memory, the least recently used pages are swapped out to disk to make room for new pages.

📱Real-world scenario 4: Content Delivery Networks (CDNs) often use LRU caches to store frequently accessed content closer to users, reducing latency and improving delivery speed.

💡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

Consider multiple approaches before coding. Mentioning alternatives shows breadth of knowledge.

⚠️ Watch Out

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

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: October 25, 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

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

@AlgoMasterJul 13

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 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.

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

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 "LRU Cache"?

For this medium-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?