Facebook Pixel

460. LFU Cache

HardDesignHash TableLinked ListDoubly-Linked List
Leetcode Link

Problem Description

This problem asks you to implement a Least Frequently Used (LFU) cache data structure with the following requirements:

What is an LFU Cache? An LFU cache evicts the least frequently used item when the cache reaches its capacity. Each item has a use counter that tracks how many times it has been accessed.

Required Operations:

  1. LFUCache(int capacity): Initialize the cache with a given capacity.

  2. get(int key):

    • If the key exists in the cache, return its value
    • If the key doesn't exist, return -1
    • When a key is accessed, its use counter increases by 1

  3. put(int key, int value):

    • If the key already exists, update its value
    • If the key doesn't exist, insert it into the cache
    • When inserting a new key and the cache is at capacity, remove the least frequently used key first
    • A newly inserted key starts with a use counter of 1
    • Accessing a key (either updating or inserting) increases its use counter by 1

Tie-Breaking Rule: When multiple keys have the same frequency (use counter), the Least Recently Used (LRU) among them should be evicted. This means if two keys have been used the same number of times, remove the one that was accessed least recently.

Performance Requirement: Both get and put operations must run in O(1) average time complexity.

Example Scenario:

  • If capacity is 2 and you insert keys A and B, both have frequency 1
  • If you access A twice, A has frequency 3 and B has frequency 1
  • When inserting a new key C at capacity, B gets evicted (lowest frequency)
  • If both A and B had frequency 2, the one accessed least recently would be evicted

The challenge is designing a data structure that can track both frequency counts and recency of access while maintaining O(1) operations for get, put, and eviction.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

To achieve O(1) operations for an LFU cache, we need to efficiently track two things: frequency counts and the order of access within each frequency group.

The key insight is that we need a two-level organization:

  1. First level: Group nodes by their frequency
  2. Second level: Within each frequency group, maintain the order of access (for LRU tie-breaking)

Think of it like organizing books on shelves - each shelf represents a frequency level (1 time used, 2 times used, etc.), and books on each shelf are ordered by when they were last touched.

Why HashMap + Doubly Linked Lists?

For O(1) access to any key, we need a HashMap that maps key -> Node. But we also need to quickly find and remove the least frequently used item.

The challenge is that when we need to evict, we must:

  • Find the minimum frequency group instantly
  • Within that group, find the least recently used item instantly
  • Remove that item in O(1) time

This leads us to use:

  • A HashMap (map): Maps each key to its node for O(1) lookup
  • Another HashMap (freq_map): Maps each frequency to a doubly linked list of nodes with that frequency
  • Doubly Linked Lists: For each frequency level, maintain nodes in LRU order (most recent at head, least recent at tail)

Why track min_freq?

When the cache is full and we need to evict, we must quickly identify which frequency group has the lowest count. Instead of searching through all frequencies, we maintain a min_freq variable that always points to the current minimum frequency level.

The frequency increment pattern:

When a node is accessed:

  1. Remove it from its current frequency list
  2. If that frequency list becomes empty and it was the minimum frequency, increment min_freq
  3. Add the node to the frequency + 1 list
  4. Always add to the head of the new list (marking it as most recently used at that frequency)

This design ensures that at any moment, we can find the least frequently used (and least recently used in case of ties) item at the tail of the freq_map[min_freq] list in O(1) time.

Solution Approach

The implementation uses three main components: Node, DoublyLinkedList, and LFUCache classes.

1. Node Class:

class Node:
    def __init__(self, key: int, value: int):
        self.key = key
        self.value = value
        self.freq = 1  # Initial frequency is 1
        self.prev = None
        self.next = None

Each node stores the key-value pair, its frequency count, and pointers for the doubly linked list.

2. DoublyLinkedList Class:

class DoublyLinkedList:
    def __init__(self):
        self.head = Node(-1, -1)  # Dummy head
        self.tail = Node(-1, -1)  # Dummy tail
        self.head.next = self.tail
        self.tail.prev = self.head

Uses dummy head and tail nodes to simplify edge cases. This list maintains nodes in LRU order within each frequency level.

Key operations:

  • add_first(node): Adds a node right after the head (most recently used position)
  • remove(node): Removes a node from the list in O(1) time
  • remove_last(): Removes the node before tail (least recently used)
  • is_empty(): Checks if the list contains any real nodes

3. LFUCache Class:

The cache maintains:

  • capacity: Maximum number of items
  • min_freq: Current minimum frequency in the cache
  • map: HashMap mapping key -> Node
  • freq_map: HashMap mapping frequency -> DoublyLinkedList

Get Operation:

def get(self, key: int) -> int:
    if key not in self.map:
        return -1
    node = self.map[key]
    self.incr_freq(node)  # Increment frequency
    return node.value

Put Operation:

def put(self, key: int, value: int) -> None:
    if key in self.map:
        # Update existing key
        node = self.map[key]
        node.value = value
        self.incr_freq(node)
    else:
        # Insert new key
        if len(self.map) == self.capacity:
            # Evict LFU item
            ls = self.freq_map[self.min_freq]
            node = ls.remove_last()  # Remove LRU from min frequency
            self.map.pop(node.key)
      
        # Create and add new node
        node = Node(key, value)
        self.add_node(node)
        self.map[key] = node
        self.min_freq = 1  # New node has frequency 1

Increment Frequency Helper:

def incr_freq(self, node: Node) -> None:
    freq = node.freq
    ls = self.freq_map[freq]
    ls.remove(node)  # Remove from current frequency list
  
    if ls.is_empty():
        self.freq_map.pop(freq)  # Clean up empty frequency
        if freq == self.min_freq:
            self.min_freq += 1  # Update min_freq if needed
  
    node.freq += 1
    self.add_node(node)  # Add to new frequency list

Add Node Helper:

def add_node(self, node: Node) -> None:
    freq = node.freq
    ls = self.freq_map[freq]  # Get or create list for this frequency
    ls.add_first(node)  # Add as most recently used
    self.freq_map[freq] = ls

Time Complexity:

  • get: O(1) - HashMap lookup + list operations
  • put: O(1) - HashMap operations + list operations
  • Space: O(capacity) for storing the cache items

The solution elegantly handles the LFU eviction policy with LRU tie-breaking by maintaining a two-level structure where frequencies map to ordered lists, ensuring all operations remain O(1).

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a concrete example with capacity 2 to see how the LFU cache operates:

Initial State:

  • Cache capacity: 2
  • Cache is empty
  • min_freq = 0

Step 1: put(1, 10)

  • Cache is not full, create new node with key=1, value=10, freq=1
  • Add node to frequency 1's linked list
  • Update min_freq = 1
  • State: 
    map: {1: Node(1,10,freq=1)}
freq_map: {1: [Node(1,10)]}
min_freq: 1

Step 2: put(2, 20)

  • Cache is not full, create new node with key=2, value=20, freq=1
  • Add node to frequency 1's linked list (at head, so it's most recent)
  • State: 
    map: {1: Node(1,10,freq=1), 2: Node(2,20,freq=1)}
freq_map: {1: [Node(2,20) -> Node(1,10)]}  // 2 is more recent
min_freq: 1

Step 3: get(1)

  • Find node with key=1 in map
  • Increment its frequency from 1 to 2:
    • Remove Node(1,10) from frequency 1's list
    • Frequency 1's list now only has Node(2,20)
    • Add Node(1,10) to frequency 2's list
  • Return value 10
  • State: 
    map: {1: Node(1,10,freq=2), 2: Node(2,20,freq=1)}
freq_map: {1: [Node(2,20)], 2: [Node(1,10)]}
min_freq: 1  // Still 1 because freq_map[1] is not empty

Step 4: put(3, 30)

  • Cache is full (size = 2), need to evict
  • Look at freq_map[min_freq] which is freq_map[1] containing [Node(2,20)]
  • Remove the least recently used from minimum frequency (Node(2,20))
  • Remove key=2 from map
  • Add new Node(3,30) with freq=1
  • Update min_freq = 1
  • State: 
    map: {1: Node(1,10,freq=2), 3: Node(3,30,freq=1)}
freq_map: {1: [Node(3,30)], 2: [Node(1,10)]}
min_freq: 1

Step 5: get(3)

  • Find node with key=3 in map
  • Increment its frequency from 1 to 2:
    • Remove Node(3,30) from frequency 1's list
    • Frequency 1's list becomes empty, so remove it from freq_map
    • Since freq=1 was min_freq and now empty, increment min_freq = 2
    • Add Node(3,30) to frequency 2's list (at head)
  • Return value 30
  • State: 
    map: {1: Node(1,10,freq=2), 3: Node(3,30,freq=2)}
freq_map: {2: [Node(3,30) -> Node(1,10)]}  // 3 is more recent
min_freq: 2

Step 6: put(4, 40)

  • Cache is full, need to evict
  • Look at freq_map[min_freq] which is freq_map[2] containing [Node(3,30) -> Node(1,10)]
  • Remove the least recently used from minimum frequency (tail = Node(1,10))
  • Remove key=1 from map
  • Add new Node(4,40) with freq=1
  • Update min_freq = 1 (new node always has frequency 1)
  • State: 
    map: {3: Node(3,30,freq=2), 4: Node(4,40,freq=1)}
freq_map: {1: [Node(4,40)], 2: [Node(3,30)]}
min_freq: 1

This example demonstrates:

  1. How nodes move between frequency lists when accessed
  2. How LRU ordering within each frequency list handles tie-breaking
  3. How min_freq tracks the lowest frequency for efficient eviction
  4. How the data structure maintains O(1) operations throughout

Solution Implementation

1from collections import defaultdict
2from typing import Optional
3
4
5class Node:
6    """Node for doubly linked list to store cache entries."""
7  
8    def __init__(self, key: int, value: int) -> None:
9        self.key = key
10        self.value = value
11        self.freq = 1  # Frequency counter starts at 1
12        self.prev: Optional[Node] = None
13        self.next: Optional[Node] = None
14
15
16class DoublyLinkedList:
17    """Doubly linked list to maintain nodes with same frequency in LRU order."""
18  
19    def __init__(self) -> None:
20        # Create dummy head and tail nodes for easier manipulation
21        self.head = Node(-1, -1)
22        self.tail = Node(-1, -1)
23        self.head.next = self.tail
24        self.tail.prev = self.head
25
26    def add_first(self, node: Node) -> None:
27        """Add node right after head (most recently used position)."""
28        node.prev = self.head
29        node.next = self.head.next
30        self.head.next.prev = node
31        self.head.next = node
32
33    def remove(self, node: Node) -> Node:
34        """Remove a specific node from the list."""
35        node.next.prev = node.prev
36        node.prev.next = node.next
37        node.next = None
38        node.prev = None
39        return node
40
41    def remove_last(self) -> Node:
42        """Remove and return the least recently used node (before tail)."""
43        return self.remove(self.tail.prev)
44
45    def is_empty(self) -> bool:
46        """Check if the list is empty (only contains dummy nodes)."""
47        return self.head.next == self.tail
48
49
50class LFUCache:
51    """
52    Least Frequently Used (LFU) cache implementation.
53    Evicts least frequently used items when capacity is reached.
54    For items with same frequency, evicts least recently used.
55    """
56  
57    def __init__(self, capacity: int) -> None:
58        self.capacity = capacity
59        self.min_freq = 0  # Track minimum frequency for eviction
60        self.node_map: dict[int, Node] = {}  # Map from key to node
61        self.freq_map: defaultdict[int, DoublyLinkedList] = defaultdict(DoublyLinkedList)  # Map from frequency to list of nodes
62
63    def get(self, key: int) -> int:
64        """
65        Get value for the given key.
66        Returns -1 if key doesn't exist.
67        """
68        # Handle edge cases
69        if self.capacity == 0 or key not in self.node_map:
70            return -1
71      
72        # Get node and update its frequency
73        node = self.node_map[key]
74        self._increment_frequency(node)
75        return node.value
76
77    def put(self, key: int, value: int) -> None:
78        """
79        Insert or update key-value pair in cache.
80        Evicts LFU item if cache is at capacity.
81        """
82        # Handle zero capacity
83        if self.capacity == 0:
84            return
85      
86        # Update existing key
87        if key in self.node_map:
88            node = self.node_map[key]
89            node.value = value
90            self._increment_frequency(node)
91            return
92      
93        # Evict LFU item if at capacity
94        if len(self.node_map) == self.capacity:
95            freq_list = self.freq_map[self.min_freq]
96            evicted_node = freq_list.remove_last()
97            del self.node_map[evicted_node.key]
98      
99        # Add new node
100        node = Node(key, value)
101        self._add_node(node)
102        self.node_map[key] = node
103        self.min_freq = 1  # New node has frequency 1
104
105    def _increment_frequency(self, node: Node) -> None:
106        """
107        Increment frequency of a node and move it to appropriate frequency list.
108        """
109        freq = node.freq
110        freq_list = self.freq_map[freq]
111      
112        # Remove node from current frequency list
113        freq_list.remove(node)
114      
115        # Clean up empty frequency list and update min_freq if needed
116        if freq_list.is_empty():
117            del self.freq_map[freq]
118            if freq == self.min_freq:
119                self.min_freq += 1
120      
121        # Increment frequency and add to new frequency list
122        node.freq += 1
123        self._add_node(node)
124
125    def _add_node(self, node: Node) -> None:
126        """
127        Add node to the frequency list corresponding to its frequency.
128        """
129        freq = node.freq
130        freq_list = self.freq_map[freq]
131        freq_list.add_first(node)
132
133
134# Your LFUCache object will be instantiated and called as such:
135# obj = LFUCache(capacity)
136# param_1 = obj.get(key)
137# obj.put(key, value)
138
1class LFUCache {
2    // Map to store key-node pairs for O(1) access
3    private final Map<Integer, Node> cache;
4    // Map to store frequency-list pairs, where each list contains nodes with same frequency
5    private final Map<Integer, DoublyLinkedList> frequencyMap;
6    // Maximum capacity of the cache
7    private final int capacity;
8    // Track the minimum frequency in the cache for eviction
9    private int minFrequency;
10
11    /**
12     * Initialize the LFU cache with given capacity
13     * @param capacity Maximum number of key-value pairs the cache can hold
14     */
15    public LFUCache(int capacity) {
16        this.capacity = capacity;
17        this.cache = new HashMap<>(capacity, 1);
18        this.frequencyMap = new HashMap<>();
19        this.minFrequency = 0;
20    }
21
22    /**
23     * Get the value of the key if it exists in the cache
24     * @param key The key to look up
25     * @return The value associated with the key, or -1 if key doesn't exist
26     */
27    public int get(int key) {
28        // Handle edge case of zero capacity
29        if (capacity == 0) {
30            return -1;
31        }
32      
33        // Key not found in cache
34        if (!cache.containsKey(key)) {
35            return -1;
36        }
37      
38        // Key exists - update frequency and return value
39        Node node = cache.get(key);
40        incrementFrequency(node);
41        return node.value;
42    }
43
44    /**
45     * Update the value of the key if present, otherwise insert the key-value pair
46     * @param key The key to insert or update
47     * @param value The value to associate with the key
48     */
49    public void put(int key, int value) {
50        // Handle edge case of zero capacity
51        if (capacity == 0) {
52            return;
53        }
54      
55        // Update existing key
56        if (cache.containsKey(key)) {
57            Node node = cache.get(key);
58            node.value = value;
59            incrementFrequency(node);
60            return;
61        }
62      
63        // Remove least frequently used item if cache is full
64        if (cache.size() == capacity) {
65            DoublyLinkedList minFrequencyList = frequencyMap.get(minFrequency);
66            Node nodeToRemove = minFrequencyList.removeLast();
67            cache.remove(nodeToRemove.key);
68        }
69      
70        // Add new node to cache
71        Node newNode = new Node(key, value);
72        addNodeToFrequencyMap(newNode);
73        cache.put(key, newNode);
74        minFrequency = 1; // New node always has frequency 1
75    }
76
77    /**
78     * Increment the frequency of a node and move it to appropriate frequency list
79     * @param node The node whose frequency needs to be incremented
80     */
81    private void incrementFrequency(Node node) {
82        int currentFrequency = node.frequency;
83      
84        // Remove node from current frequency list
85        DoublyLinkedList currentList = frequencyMap.get(currentFrequency);
86        currentList.remove(node);
87      
88        // Clean up empty frequency list and update minFrequency if needed
89        if (currentList.isEmpty()) {
90            frequencyMap.remove(currentFrequency);
91            if (currentFrequency == minFrequency) {
92                minFrequency++;
93            }
94        }
95      
96        // Increment frequency and add to new frequency list
97        node.frequency++;
98        addNodeToFrequencyMap(node);
99    }
100
101    /**
102     * Add a node to the frequency map based on its current frequency
103     * @param node The node to add to frequency map
104     */
105    private void addNodeToFrequencyMap(Node node) {
106        int frequency = node.frequency;
107      
108        // Get or create the list for this frequency
109        DoublyLinkedList list = frequencyMap.computeIfAbsent(frequency, 
110            k -> new DoublyLinkedList());
111      
112        // Add node to the front of the list (most recently used)
113        list.addFirst(node);
114    }
115
116    /**
117     * Node class representing a cache entry
118     */
119    private static class Node {
120        int key;
121        int value;
122        int frequency;
123        Node prev;
124        Node next;
125
126        Node(int key, int value) {
127            this.key = key;
128            this.value = value;
129            this.frequency = 1; // Initial frequency is always 1
130        }
131    }
132
133    /**
134     * Doubly linked list to maintain LRU order within same frequency
135     */
136    private static class DoublyLinkedList {
137        // Dummy head and tail nodes to simplify operations
138        private final Node head;
139        private final Node tail;
140
141        public DoublyLinkedList() {
142            // Initialize dummy nodes
143            head = new Node(-1, -1);
144            tail = new Node(-1, -1);
145            head.next = tail;
146            tail.prev = head;
147        }
148
149        /**
150         * Add a node to the front of the list (most recently used position)
151         * @param node The node to add
152         */
153        public void addFirst(Node node) {
154            node.prev = head;
155            node.next = head.next;
156            head.next.prev = node;
157            head.next = node;
158        }
159
160        /**
161         * Remove a specific node from the list
162         * @param node The node to remove
163         * @return The removed node
164         */
165        public Node remove(Node node) {
166            node.next.prev = node.prev;
167            node.prev.next = node.next;
168            node.next = null;
169            node.prev = null;
170            return node;
171        }
172
173        /**
174         * Remove the last node from the list (least recently used)
175         * @return The removed node
176         */
177        public Node removeLast() {
178            return remove(tail.prev);
179        }
180
181        /**
182         * Check if the list is empty
183         * @return true if list is empty, false otherwise
184         */
185        public boolean isEmpty() {
186            return head.next == tail;
187        }
188    }
189}
190
1class Node {
2public:
3    int key;
4    int value;
5    int freq;
6    Node* prev;
7    Node* next;
8  
9    // Constructor to initialize a node with key-value pair and frequency 1
10    Node(int key, int value) {
11        this->key = key;
12        this->value = value;
13        this->freq = 1;
14        this->prev = nullptr;
15        this->next = nullptr;
16    }
17};
18
19class DoublyLinkedList {
20public:
21    Node* head;  // Dummy head node
22    Node* tail;  // Dummy tail node
23  
24    // Initialize doubly linked list with dummy head and tail
25    DoublyLinkedList() {
26        this->head = new Node(-1, -1);
27        this->tail = new Node(-1, -1);
28        this->head->next = this->tail;
29        this->tail->prev = this->head;
30    }
31  
32    // Add a node right after the dummy head (most recently used position)
33    void addFirst(Node* node) {
34        node->prev = this->head;
35        node->next = this->head->next;
36        this->head->next->prev = node;
37        this->head->next = node;
38    }
39  
40    // Remove a specific node from the list and return it
41    Node* remove(Node* node) {
42        node->next->prev = node->prev;
43        node->prev->next = node->next;
44        node->next = nullptr;
45        node->prev = nullptr;
46        return node;
47    }
48  
49    // Remove and return the least recently used node (node before dummy tail)
50    Node* removeLast() {
51        return remove(this->tail->prev);
52    }
53  
54    // Check if the list is empty (only contains dummy nodes)
55    bool isEmpty() {
56        return this->head->next == this->tail;
57    }
58};
59
60class LFUCache {
61public:
62    // Initialize LFU cache with given capacity
63    LFUCache(int capacity) {
64        this->capacity = capacity;
65        this->minFreq = 0;
66    }
67  
68    // Get value for the given key, return -1 if key doesn't exist
69    int get(int key) {
70        // Handle edge case: zero capacity or key not found
71        if (capacity == 0 || keyToNodeMap.find(key) == keyToNodeMap.end()) {
72            return -1;
73        }
74      
75        // Get the node and increment its frequency
76        Node* node = keyToNodeMap[key];
77        incrementFrequency(node);
78        return node->value;
79    }
80  
81    // Put key-value pair into cache
82    void put(int key, int value) {
83        // Edge case: zero capacity cache
84        if (capacity == 0) {
85            return;
86        }
87      
88        // If key exists, update its value and increment frequency
89        if (keyToNodeMap.find(key) != keyToNodeMap.end()) {
90            Node* node = keyToNodeMap[key];
91            node->value = value;
92            incrementFrequency(node);
93            return;
94        }
95      
96        // If cache is full, evict the least frequently used item
97        if (keyToNodeMap.size() == capacity) {
98            DoublyLinkedList* minFreqList = frequencyToListMap[minFreq];
99            Node* nodeToEvict = minFreqList->removeLast();
100            keyToNodeMap.erase(nodeToEvict->key);
101            delete nodeToEvict;  // Free memory
102        }
103      
104        // Create new node and add it to the cache
105        Node* newNode = new Node(key, value);
106        addNodeToFrequencyList(newNode);
107        keyToNodeMap[key] = newNode;
108        minFreq = 1;  // New node always has frequency 1
109    }
110
111private:
112    int capacity;                                           // Maximum cache capacity
113    int minFreq;                                            // Current minimum frequency in cache
114    unordered_map<int, Node*> keyToNodeMap;               // Map from key to node pointer
115    unordered_map<int, DoublyLinkedList*> frequencyToListMap;  // Map from frequency to list of nodes
116  
117    // Increment the frequency of a node and move it to appropriate frequency list
118    void incrementFrequency(Node* node) {
119        int currentFreq = node->freq;
120        DoublyLinkedList* currentList = frequencyToListMap[currentFreq];
121      
122        // Remove node from current frequency list
123        currentList->remove(node);
124      
125        // If current frequency list becomes empty, clean up
126        if (currentList->isEmpty()) {
127            frequencyToListMap.erase(currentFreq);
128            // Update minFreq if necessary
129            if (currentFreq == minFreq) {
130                minFreq++;
131            }
132        }
133      
134        // Increment frequency and add to new frequency list
135        node->freq++;
136        addNodeToFrequencyList(node);
137    }
138  
139    // Add a node to its corresponding frequency list
140    void addNodeToFrequencyList(Node* node) {
141        int freq = node->freq;
142      
143        // Create new frequency list if it doesn't exist
144        if (frequencyToListMap.find(freq) == frequencyToListMap.end()) {
145            frequencyToListMap[freq] = new DoublyLinkedList();
146        }
147      
148        // Add node to the front of the frequency list (most recently used)
149        DoublyLinkedList* freqList = frequencyToListMap[freq];
150        freqList->addFirst(node);
151    }
152};
153
154/**
155 * Your LFUCache object will be instantiated and called as such:
156 * LFUCache* obj = new LFUCache(capacity);
157 * int param_1 = obj->get(key);
158 * obj->put(key,value);
159 */
160
1// Node structure for LFU Cache
2interface Node {
3    key: number;
4    value: number;
5    freq: number;
6    prev: Node | null;
7    next: Node | null;
8}
9
10// Create a new node with key-value pair and frequency 1
11function createNode(key: number, value: number): Node {
12    return {
13        key: key,
14        value: value,
15        freq: 1,
16        prev: null,
17        next: null
18    };
19}
20
21// Doubly linked list structure
22interface DoublyLinkedList {
23    head: Node;
24    tail: Node;
25}
26
27// Initialize doubly linked list with dummy head and tail
28function createDoublyLinkedList(): DoublyLinkedList {
29    const head = createNode(-1, -1);
30    const tail = createNode(-1, -1);
31    head.next = tail;
32    tail.prev = head;
33    return { head, tail };
34}
35
36// Add a node right after the dummy head (most recently used position)
37function addFirst(list: DoublyLinkedList, node: Node): void {
38    node.prev = list.head;
39    node.next = list.head.next;
40    if (list.head.next) {
41        list.head.next.prev = node;
42    }
43    list.head.next = node;
44}
45
46// Remove a specific node from the list and return it
47function removeNode(node: Node): Node {
48    if (node.prev) {
49        node.prev.next = node.next;
50    }
51    if (node.next) {
52        node.next.prev = node.prev;
53    }
54    node.next = null;
55    node.prev = null;
56    return node;
57}
58
59// Remove and return the least recently used node (node before dummy tail)
60function removeLast(list: DoublyLinkedList): Node | null {
61    if (list.tail.prev && list.tail.prev !== list.head) {
62        return removeNode(list.tail.prev);
63    }
64    return null;
65}
66
67// Check if the list is empty (only contains dummy nodes)
68function isEmpty(list: DoublyLinkedList): boolean {
69    return list.head.next === list.tail;
70}
71
72// Global variables for LFU Cache
73let capacity: number = 0;
74let minFreq: number = 0;
75let keyToNodeMap: Map<number, Node> = new Map();
76let frequencyToListMap: Map<number, DoublyLinkedList> = new Map();
77
78// Initialize LFU cache with given capacity
79function LFUCache(cap: number): void {
80    capacity = cap;
81    minFreq = 0;
82    keyToNodeMap = new Map();
83    frequencyToListMap = new Map();
84}
85
86// Add a node to its corresponding frequency list
87function addNodeToFrequencyList(node: Node): void {
88    const freq = node.freq;
89  
90    // Create new frequency list if it doesn't exist
91    if (!frequencyToListMap.has(freq)) {
92        frequencyToListMap.set(freq, createDoublyLinkedList());
93    }
94  
95    // Add node to the front of the frequency list (most recently used)
96    const freqList = frequencyToListMap.get(freq)!;
97    addFirst(freqList, node);
98}
99
100// Increment the frequency of a node and move it to appropriate frequency list
101function incrementFrequency(node: Node): void {
102    const currentFreq = node.freq;
103    const currentList = frequencyToListMap.get(currentFreq);
104  
105    if (!currentList) return;
106  
107    // Remove node from current frequency list
108    removeNode(node);
109  
110    // If current frequency list becomes empty, clean up
111    if (isEmpty(currentList)) {
112        frequencyToListMap.delete(currentFreq);
113        // Update minFreq if necessary
114        if (currentFreq === minFreq) {
115            minFreq++;
116        }
117    }
118  
119    // Increment frequency and add to new frequency list
120    node.freq++;
121    addNodeToFrequencyList(node);
122}
123
124// Get value for the given key, return -1 if key doesn't exist
125function get(key: number): number {
126    // Handle edge case: zero capacity or key not found
127    if (capacity === 0 || !keyToNodeMap.has(key)) {
128        return -1;
129    }
130  
131    // Get the node and increment its frequency
132    const node = keyToNodeMap.get(key)!;
133    incrementFrequency(node);
134    return node.value;
135}
136
137// Put key-value pair into cache
138function put(key: number, value: number): void {
139    // Edge case: zero capacity cache
140    if (capacity === 0) {
141        return;
142    }
143  
144    // If key exists, update its value and increment frequency
145    if (keyToNodeMap.has(key)) {
146        const node = keyToNodeMap.get(key)!;
147        node.value = value;
148        incrementFrequency(node);
149        return;
150    }
151  
152    // If cache is full, evict the least frequently used item
153    if (keyToNodeMap.size === capacity) {
154        const minFreqList = frequencyToListMap.get(minFreq);
155        if (minFreqList) {
156            const nodeToEvict = removeLast(minFreqList);
157            if (nodeToEvict) {
158                keyToNodeMap.delete(nodeToEvict.key);
159            }
160        }
161    }
162  
163    // Create new node and add it to the cache
164    const newNode = createNode(key, value);
165    addNodeToFrequencyList(newNode);
166    keyToNodeMap.set(key, newNode);
167    minFreq = 1;  // New node always has frequency 1
168}
169

Time and Space Complexity

Time Complexity:

  • get(key): O(1)

    • Checking if key exists in map: O(1) (hash map lookup)
    • Calling incr_freq(): O(1) (involves removing and adding node to doubly linked list)
    • Return value: O(1)

  • put(key, value): O(1)

    • Checking if key exists in map: O(1) (hash map lookup)
    • If key exists, update value and call incr_freq(): O(1)
    • If at capacity, remove LFU node: O(1) (remove from tail of min_freq list)
    • Create new node and call add_node(): O(1)
    • Update map and min_freq: O(1)

  • Helper functions:

    • incr_freq(): O(1) - removes node from current frequency list, updates frequency, adds to new frequency list
    • add_node(): O(1) - adds node to head of frequency list
    • add_first(): O(1) - pointer manipulation in doubly linked list
    • remove(): O(1) - pointer manipulation in doubly linked list
    • remove_last(): O(1) - calls remove on tail's previous node
    • is_empty(): O(1) - simple comparison

Space Complexity: O(capacity)

  • self.map: O(n) where n ≤ capacity (stores at most capacity nodes)
  • self.freq_map: O(n) in worst case (each node could have different frequency)
  • Each Node: O(1) space, total O(n) for all nodes
  • Each DoublyLinkedList: O(1) overhead (just head and tail sentinels), but contains nodes already counted
  • Total: O(capacity) since the cache never stores more than capacity items

Common Pitfalls

1. Forgetting to Handle Zero Capacity Edge Case

One of the most common pitfalls is not properly handling when the cache is initialized with capacity 0. This can lead to unexpected behavior or errors when trying to perform operations.

Problem Code:

class LFUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        # ... other initialization
  
    def put(self, key: int, value: int) -> None:
        # Missing zero capacity check
        if key in self.node_map:
            # update logic
        else:
            if len(self.node_map) == self.capacity:  # This will evict when capacity=0!
                # eviction logic
            # add new node

Solution: Always check for zero capacity at the beginning of both get and put methods:

def get(self, key: int) -> int:
    if self.capacity == 0:  # Handle zero capacity
        return -1
    # ... rest of logic

def put(self, key: int, value: int) -> None:
    if self.capacity == 0:  # Handle zero capacity
        return
    # ... rest of logic

2. Incorrectly Updating min_freq When Removing Nodes

A critical pitfall is not properly maintaining the min_freq variable when removing nodes from frequency lists, especially when the minimum frequency list becomes empty.

Problem Code:

def _increment_frequency(self, node: Node) -> None:
    freq = node.freq
    freq_list = self.freq_map[freq]
    freq_list.remove(node)
  
    # Forgot to update min_freq when the list becomes empty!
    if freq_list.is_empty():
        del self.freq_map[freq]
        # Missing: if freq == self.min_freq: self.min_freq += 1
  
    node.freq += 1
    self._add_node(node)

Solution: Always update min_freq when the minimum frequency list becomes empty:

if freq_list.is_empty():
    del self.freq_map[freq]
    if freq == self.min_freq:
        self.min_freq += 1  # Critical update!

3. Not Resetting min_freq When Adding New Nodes

When adding a new node to the cache, forgetting to reset min_freq to 1 can cause incorrect eviction behavior.

Problem Code:

def put(self, key: int, value: int) -> None:
    if key not in self.node_map:
        # eviction logic if needed
        node = Node(key, value)
        self._add_node(node)
        self.node_map[key] = node
        # Forgot to set: self.min_freq = 1

Solution: Always set min_freq = 1 when adding a new node:

node = Node(key, value)
self._add_node(node)
self.node_map[key] = node
self.min_freq = 1  # New nodes always have frequency 1

4. Memory Leak from Not Properly Cleaning Up Node Pointers

When removing nodes from the doubly linked list, failing to set the prev and next pointers to None can cause memory leaks.

Problem Code:

def remove(self, node: Node) -> Node:
    node.next.prev = node.prev
    node.prev.next = node.next
    # Forgot to clean up node's pointers!
    return node

Solution: Always clean up the removed node's pointers:

def remove(self, node: Node) -> Node:
    node.next.prev = node.prev
    node.prev.next = node.next
    node.next = None  # Clean up
    node.prev = None  # Clean up
    return node

5. Using Regular Dict Instead of defaultdict

Using a regular dictionary for freq_map requires extra code to check and create new lists for each frequency.

Problem Code:

self.freq_map: dict[int, DoublyLinkedList] = {}

def _add_node(self, node: Node) -> None:
    freq = node.freq
    if freq not in self.freq_map:  # Extra check needed
        self.freq_map[freq] = DoublyLinkedList()
    freq_list = self.freq_map[freq]
    freq_list.add_first(node)

Solution: Use defaultdict to automatically create new lists:

from collections import defaultdict

self.freq_map: defaultdict[int, DoublyLinkedList] = defaultdict(DoublyLinkedList)

def _add_node(self, node: Node) -> None:
    freq = node.freq
    freq_list = self.freq_map[freq]  # Automatically creates new list if needed
    freq_list.add_first(node)

These pitfalls can cause subtle bugs that are difficult to debug, especially under edge cases. Careful attention to state management and edge case handling is crucial for a correct LFU cache implementation.

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Which of the following is a good use case for backtracking?

Recommended Readings

Linked List Cycle

Linked List Cycle Given a linked list with potentially a loop determine whether the linked list from the first node contains a cycle in it For bonus points do this with constant space Parameters nodes The first node of a linked list with potentially a loop Result Whether there is a loop contained

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More