LeetCode Problem Workspace
Frequency Tracker
Design a data structure to track values and answer frequency-related queries efficiently using hash tables.
2
Topics
6
Code langs
3
Related
Practice Focus
Medium · Hash Table plus Design
Answer-first summary
Design a data structure to track values and answer frequency-related queries efficiently using hash tables.
Ace coding interviews with Interview AiBoxInterview AiBox guidance for Hash Table plus Design
This problem requires you to design a data structure that manages numbers and answers frequency-related queries. Using a hash table or similar design helps efficiently track each number's frequency and supports operations like adding, deleting, and checking if a specific frequency exists. Proper implementation ensures the operations run within the problem's time and space constraints.
Problem Statement
You need to design a class, FrequencyTracker, that supports three operations: add(number), deleteOne(number), and hasFrequency(frequency). The add(number) operation adds a number to the tracker, the deleteOne(number) removes one occurrence of a number, and the hasFrequency(frequency) checks if any number appears with the given frequency. The tracker must be efficient enough to handle up to 2 * 10^5 operations.
Your task is to implement this FrequencyTracker class, using an efficient design that leverages hash tables to track the frequency of numbers and handle operations within the given constraints.
Examples
Example 1
Input: See original problem statement.
Output: See original problem statement.
Input ["FrequencyTracker", "add", "add", "hasFrequency"] [[], [3], [3], [2]] Output [null, null, null, true]
Explanation FrequencyTracker frequencyTracker = new FrequencyTracker(); frequencyTracker.add(3); // The data structure now contains [3] frequencyTracker.add(3); // The data structure now contains [3, 3] frequencyTracker.hasFrequency(2); // Returns true, because 3 occurs twice
Example 2
Input: See original problem statement.
Output: See original problem statement.
Input ["FrequencyTracker", "add", "deleteOne", "hasFrequency"] [[], [1], [1], [1]] Output [null, null, null, false]
Explanation FrequencyTracker frequencyTracker = new FrequencyTracker(); frequencyTracker.add(1); // The data structure now contains [1] frequencyTracker.deleteOne(1); // The data structure becomes empty [] frequencyTracker.hasFrequency(1); // Returns false, because the data structure is empty
Example 3
Input: See original problem statement.
Output: See original problem statement.
Input ["FrequencyTracker", "hasFrequency", "add", "hasFrequency"] [[], [2], [3], [1]] Output [null, false, null, true]
Explanation FrequencyTracker frequencyTracker = new FrequencyTracker(); frequencyTracker.hasFrequency(2); // Returns false, because the data structure is empty frequencyTracker.add(3); // The data structure now contains [3] frequencyTracker.hasFrequency(1); // Returns true, because 3 occurs once
Constraints
- 1 <= number <= 105
- 1 <= frequency <= 105
- At most, 2 * 105 calls will be made to add, deleteOne, and hasFrequency in total.
Solution Approach
Use a Hash Table for Frequency Tracking
The core idea is to use a hash table (or dictionary) where the keys represent the numbers and the values represent the frequency of those numbers. This allows for fast access and updates when performing the add or deleteOne operations.
Track Frequency of Frequencies
In addition to tracking the frequencies of numbers, we need to maintain another hash table that tracks the frequency of each frequency. This helps answer the hasFrequency(frequency) query efficiently, as we can check if any frequency exists in constant time.
Optimize Operations for Constraints
Given the problem's constraints, operations should be optimized to work in O(1) time for add, deleteOne, and hasFrequency to handle up to 2 * 10^5 operations efficiently. Proper updates and checks on the hash tables ensure that these operations are performed optimally.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
The time complexity for add, deleteOne, and hasFrequency operations is O(1) under normal circumstances, as hash table lookups, insertions, and deletions all operate in constant time. The space complexity depends on the number of unique numbers and their frequencies, which can scale with the input size.
What Interviewers Usually Probe
- Check if the candidate correctly uses hash tables for efficient frequency management.
- Evaluate the approach for handling multiple operations efficiently under large constraints.
- Assess how the candidate tracks the frequency of frequencies to optimize the
hasFrequencyquery.
Common Pitfalls or Variants
Common pitfalls
- Failing to handle cases where a number's frequency drops to zero after a delete operation.
- Using inefficient data structures that lead to time complexity issues with the large number of operations.
- Not correctly updating the frequency count in the second hash table for
hasFrequencyqueries.
Follow-up variants
- Track the frequency of multiple numbers with the ability to reset frequencies.
- Support additional operations like
getMostFrequent()to return the number with the highest frequency. - Design a version that supports querying for the least frequent number.
FAQ
What is the best way to track frequencies in the FrequencyTracker problem?
The best approach is to use a hash table to store the number as the key and its frequency as the value. Additionally, use another hash table to store the frequencies of frequencies for efficient querying.
How do I handle the hasFrequency(frequency) query efficiently?
You can handle hasFrequency(frequency) efficiently by maintaining a second hash table that tracks how many numbers have a given frequency, allowing for O(1) lookups.
What happens if a number's frequency drops to zero?
When the frequency of a number drops to zero after a deleteOne operation, ensure that both the number's frequency and the frequency of that frequency in the second hash table are updated correctly.
How does the solution scale with large input sizes?
The solution scales well as each operation (add, deleteOne, hasFrequency) runs in O(1) time, ensuring that the solution can handle up to 2 * 10^5 operations efficiently.
What is the time and space complexity of the solution?
The time complexity for each operation is O(1), and the space complexity depends on the number of unique numbers and their frequencies, scaling with the input size.
Solution
Solution 1: Hash Table
We define two hash tables, where $cnt$ is used to record the occurrence count of each number, and $freq$ is used to record the count of numbers with each frequency.
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)Continue Topic
hash table
Practice more edge cases under the same topic.
arrow_forwardauto_awesomeContinue Pattern
Hash Table plus Design
Expand the same solving frame across more problems.
arrow_forwardsignal_cellular_altSame Difficulty Track
Medium
Stay on this level to stabilize interview delivery.
arrow_forward