Frequency Tracker — LeetCode 2671 Python Solution
MediumDesignHash Table
- Problem
- #2671
- Pattern
- Hash Map
- Reading time
- 4 min
- Source
- leetcode.com
The problem
Design a data structure that keeps track of the values in it and answers some queries regarding their frequencies. Implement the FrequencyTracker class.
Example
- Input
- ["FrequencyTracker", "add", "add", "hasFrequency"]
- Output
- [null, null, null, true]
- Explanation
- FrequencyTracker frequencyTracker = new FrequencyTracker();
Python solution
Python
class FrequencyTracker:
def __init__(self):
self.cnt = defaultdict(int)
self.freq = defaultdict(int)
def add(self, number: int) -> None:
self.freq[self.cnt[number]] -= 1
self.cnt[number] += 1
self.freq[self.cnt[number]] += 1
def deleteOne(self, number: int) -> None:
if self.cnt[number]:
self.freq[self.cnt[number]] -= 1
self.cnt[number] -= 1
self.freq[self.cnt[number]] += 1
def hasFrequency(self, frequency: int) -> bool:
return self.freq[frequency] > 0
# Your FrequencyTracker object will be instantiated and called as such:
# obj = FrequencyTracker()
# obj.add(number)
# obj.deleteOne(number)
# param_3 = obj.hasFrequency(frequency)Complexity
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(n), where n is the number of distinct numbers auxiliary |
Pattern: Hash Map
Trade memory for time: remember what you have seen so the second pass never happens. LeetCode 2671. Frequency Tracker is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Hash Table.
The hash map guide has the Python template for the pattern and the 709 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 2671. Frequency Tracker?
- LeetCode 2671. Frequency Tracker is rated Medium on LeetCode.
- What is the time complexity of LeetCode 2671. Frequency Tracker?
- The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 2671. Frequency Tracker?
- The Python solution on this page uses O(n), where n is the number of distinct numbers auxiliary space.
- What topics does LeetCode 2671. Frequency Tracker cover?
- LeetCode 2671. Frequency Tracker is tagged Design and Hash Table on LeetCode.