#146

Medium

auto_awesomeLinked-list pointer manipulation

LeetCode Problem Workspace

LRU Cache

Implement an efficient LRU Cache using hash table and doubly-linked list to achieve O(1) operations for get and put.

hash table linked list design doubly linked list

Problem Statement

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement the LRUCache class with a constructor taking a capacity, and two functions get(key) and put(key, value) that retrieve and insert key-value pairs, respectively, while maintaining usage order.

The get and put functions must run in O(1) average time complexity. When the cache reaches its capacity, inserting a new item must evict the least recently used entry. You must combine a hash table for direct access and a doubly-linked list for tracking usage to maintain the LRU property efficiently.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

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 <= 104
0 <= value <= 105
At most 2 * 105 calls will be made to get and put.

Solution Approach

Hash Table for Fast Key Access

Use a hash table to map keys directly to nodes in the linked list. This ensures that get(key) can locate nodes in O(1) time without traversing the list, which is critical for maintaining constant-time access in the LRU cache.

Doubly-Linked List for Usage Order

Maintain a doubly-linked list where the most recently used node is moved to the head and the least recently used node is at the tail. Properly update the previous and next pointers when nodes are accessed or inserted, as incorrect pointer manipulation can break the LRU order.

Eviction on Capacity Limit

When adding a new key exceeds the cache capacity, remove the tail node from the doubly-linked list and delete its key from the hash table. This eviction step must precisely handle pointer updates to prevent dangling references and preserve list integrity.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(1) for get and put due to hash table access and constant-time list pointer updates. Space complexity is O(capacity) for storing nodes in both hash table and linked list.

What Interviewers Usually Probe

Emphasizing O(1) get and put is key to assess understanding of combined hash table and linked list design.
Watch for candidates managing head/tail pointers carefully; mismanagement indicates misunderstanding of doubly-linked list operations.
Check for clear handling of eviction when capacity is reached, as failure here often causes subtle bugs.

Common Pitfalls or Variants

Common pitfalls

Forgetting to update both previous and next pointers when moving nodes leads to broken list connections.
Neglecting to remove evicted nodes from the hash table causes memory leaks or incorrect retrievals.
Assuming a singly-linked list is sufficient; LRU eviction requires doubly-linked list for O(1) removals.

Follow-up variants

Implement LRU Cache using only a singly-linked list and analyze the trade-offs in time complexity.
Design a Most Recently Used (MRU) Cache by reversing insertion/removal logic in the linked list.
Extend LRU Cache to support a getMostRecentKey() operation in O(1) time without affecting existing operations.

FAQ

What is the best approach for implementing LRU Cache with O(1) operations?

Combine a hash table for direct key access with a doubly-linked list to maintain usage order and handle eviction efficiently.

Why does LRU Cache require a doubly-linked list instead of singly-linked?

A doubly-linked list allows O(1) removal of arbitrary nodes and easy movement to the head, which is essential for maintaining the correct LRU order.

How do you handle eviction when the cache exceeds capacity?

Remove the tail node from the doubly-linked list and delete its key from the hash table, ensuring all pointers are correctly updated.

Can the get and put operations ever exceed O(1) time in LRU Cache?

No, if implemented correctly with a hash table and doubly-linked list, all operations run in O(1) average time regardless of cache size.

What are common mistakes when manipulating pointers in LRU Cache linked list?

Typical mistakes include failing to update previous/next pointers when moving nodes, not updating head/tail correctly, and leaving evicted nodes in the hash table.

terminal

Solution

Solution 1: Hash Table + Doubly Linked List

We can implement an LRU (Least Recently Used) cache using a "hash table" and a "doubly linked list".

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

class Node:
    def __init__(self, key: int = 0, val: int = 0):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None


class LRUCache:

    def __init__(self, capacity: int):
        self.size = 0
        self.capacity = capacity
        self.cache = {}
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self.remove_node(node)
        self.add_to_head(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            self.remove_node(node)
            node.val = value
            self.add_to_head(node)
        else:
            node = Node(key, value)
            self.cache[key] = node
            self.add_to_head(node)
            self.size += 1
            if self.size > self.capacity:
                node = self.tail.prev
                self.cache.pop(node.key)
                self.remove_node(node)
                self.size -= 1

    def remove_node(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def add_to_head(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next = node
        node.next.prev = node


# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

Continue Practicing

#705 design hashset #706 design hashmap #142 linked list cycle ii