HardNo. 0460
LFU Cache — LeetCode 460 Python Solution
- Pattern
- Linked List
- Topics
- Design, Hash Table, Linked List, Doubly-Linked List
- Reading time
- 16 min
- Source
- leetcode.com
The problem
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.
Example
- Input
- ["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
- Output
- [null, null, null, 1, null, -1, 3, null, -1, 3, 4]
- Explanation
- // cnt(x) = the use counter for key x
Python solution
class Node:
def __init__(self, key: int, value: int) -> None:
self.key = key
self.value = value
self.freq = 1
self.prev = None
self.next = None
class DoublyLinkedList:
def __init__(self) -> None:
self.head = Node(-1, -1)
self.tail = Node(-1, -1)
self.head.next = self.tail
self.tail.prev = self.head
def add_first(self, node: Node) -> None:
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node
def remove(self, node: Node) -> Node:
node.next.prev = node.prev
node.prev.next = node.next
node.next, node.prev = None, None
return node
def remove_last(self) -> Node:
return self.remove(self.tail.prev)
def is_empty(self) -> bool:
return self.head.next == self.tail
class LFUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.min_freq = 0
self.map = defaultdict(Node)
self.freq_map = defaultdict(DoublyLinkedList)
def get(self, key: int) -> int:
if self.capacity == 0 or key not in self.map:
return -1
node = self.map[key]
self.incr_freq(node)
return node.value
def put(self, key: int, value: int) -> None:
if self.capacity == 0:
return
if key in self.map:
node = self.map[key]
node.value = value
self.incr_freq(node)
return
if len(self.map) == self.capacity:
ls = self.freq_map[self.min_freq]
node = ls.remove_last()
self.map.pop(node.key)
node = Node(key, value)
self.add_node(node)
self.map[key] = node
self.min_freq = 1
def incr_freq(self, node: Node) -> None:
freq = node.freq
ls = self.freq_map[freq]
ls.remove(node)
if ls.is_empty():
self.freq_map.pop(freq)
if freq == self.min_freq:
self.min_freq += 1
node.freq += 1
self.add_node(node)
def add_node(self, node: Node) -> None:
freq = node.freq
ls = self.freq_map[freq]
ls.add_first(node)
self.freq_map[freq] = ls
# Your LFUCache object will be instantiated and called as such:
# obj = LFUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)Complexity
- Time
- O(n)
- Space · auxiliary
- O(n)
Pattern: Linked List
Rewire pointers in place, with a dummy head and a saved next to keep it safe. LeetCode 460. LFU Cache is filed here because LeetCode tags it Linked List and Doubly-Linked List, which is the vocabulary this hub collects.
The linked list guide has the Python template for the pattern and the 75 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0146 | LRU Cache | Medium |
| 0432 | All O`one Data Structure | Hard |
| 1797 | Design Authentication Manager | Medium |
| 0355 | Design Twitter | Medium |
| 0705 | Design HashSet | Easy |
| 0706 | Design HashMap | Easy |
Frequently asked questions
- How hard is LeetCode 460. LFU Cache?
LeetCode 460. LFU Cache is rated Hard on LeetCode.
- What is the time complexity of LeetCode 460. LFU Cache?
The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 460. LFU Cache?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 460. LFU Cache cover?
LeetCode 460. LFU Cache is tagged Design, Hash Table, Linked List and Doubly-Linked List on LeetCode.