LRU Cache

LeetCode 146 | Difficulty: Medium

Medium

Problem Description

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 used key.

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

Example 1:

Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1);    // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2);    // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1);    // return -1 (not found)
lRUCache.get(3);    // return 3
lRUCache.get(4);    // return 4

Constraints:

- `1 <= capacity <= 3000`

- `0 <= key <= 10^4`

- `0 <= value <= 10^5`

- At most `2 * 10^5` calls will be made to `get` and `put`.

Topics: Hash Table, Linked List, Design, Doubly-Linked List

---

Approach

Hash Map

Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?

When to use

Need fast lookups, counting frequencies, finding complements/pairs.

Design

Choose the right data structures to meet the required time complexities for each operation. Consider hash maps for O(1) access, doubly-linked lists for O(1) insertion/deletion, and combining structures for complex requirements.

When to use

Implementing a data structure or system with specific operation time requirements.

Linked List

Use pointer manipulation. Common techniques: dummy head node to simplify edge cases, fast/slow pointers for cycle detection and middle finding, prev/curr/next pattern for reversal.

When to use

In-place list manipulation, cycle detection, merging lists, finding the k-th node.

---

Solutions

Solution 1: C# (Best: 544 ms)

Metric	Value
Runtime	544 ms
Memory	50.5 MB
Date	2020-01-15

Solution

public class LRUCache
{
    
private Dictionary<int, CacheItem> map = new Dictionary<int, CacheItem>();
private class CacheItem
{
    public int CacheKey { get; set; }
    public int CacheValue { get; set; }
}   
private LinkedList<CacheItem> lru = new LinkedList<CacheItem>();
    private int capacity;
    public LRUCache(int capacity) { this.capacity = capacity; }
    public int Get(int key)
    {
        if (!map.ContainsKey(key)) return -1;
        lru.Remove(map[key]);
        lru.AddLast(map[key]);
        return map[key].CacheValue;
    }
    public void Put(int key, int val)
    {
        if (map.ContainsKey(key))
        {
            map[key].CacheValue = val;
            lru.Remove(map[key]);
            lru.AddLast(map[key]);
            return;
        }
        if (map.Count >= capacity)
        {
            map.Remove(lru.First.Value.CacheKey);
            lru.RemoveFirst();
        }
        map.Add(key, new CacheItem { CacheKey = key, CacheValue = val });
        lru.AddLast(map[key]);
    }
}



/**
 * 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);
 */

---

Complexity Analysis

Approach	Time	Space
Hash Map	$O(n)$	$O(n)$
Linked List	$O(n)$	$O(1)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Hash map gives O(1) lookup — think about what to use as key vs value.
• Draw the pointer changes before coding. A dummy head node simplifies edge cases.
• Clarify the expected time complexity for each operation before choosing data structures.