Watch 10 video solutions for Frequency Tracker, a medium level problem involving Hash Table, Design. This walkthrough by ThinkCode has 639 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Design a data structure that keeps track of the values in it and answers some queries regarding their frequencies.
Implement the FrequencyTracker class.
FrequencyTracker(): Initializes the FrequencyTracker object with an empty array initially.void add(int number): Adds number to the data structure.void deleteOne(int number): Deletes one occurrence of number from the data structure. The data structure may not contain number, and in this case nothing is deleted.bool hasFrequency(int frequency): Returns true if there is a number in the data structure that occurs frequency number of times, otherwise, it returns false.
Example 1:
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 ["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 ["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 <= 1051 <= frequency <= 1052 * 105 calls will be made to add, deleteOne, and hasFrequency in total.Problem Overview: You need to design a data structure that tracks numbers and their frequencies. Three operations must be supported: add(number), deleteOne(number), and hasFrequency(frequency). The tricky part is answering whether any number currently appears exactly frequency times without scanning the entire dataset.
Approach 1: Using Two Hash Maps (O(1) time per operation, O(n) space)
This approach maintains two hash maps. The first map count[number] stores how many times each number appears. The second map freq[f] stores how many numbers currently have frequency f. When you call add, increment the number's count and update both maps. When deleteOne is called, decrease the count and update the frequency tracking map accordingly. The key insight is that hasFrequency(f) becomes a constant-time lookup: simply check whether freq[f] > 0. This avoids iterating through all numbers and is the standard solution for problems involving dynamic frequency tracking using a hash table.
Approach 2: Using a List and Counter (O(1) average time, O(n) space)
If the value range is bounded, you can replace the primary hash map with an indexed list (array) where the index represents the number and the value stores its frequency. A separate counter structure tracks how many numbers currently have each frequency. Updates happen in constant time by decrementing the old frequency bucket and incrementing the new one. The array avoids hash lookups and can be slightly faster in languages like C++ or Java. The overall logic remains identical: maintain a mapping from numbers to counts and another structure that tracks how many numbers share the same count.
Both approaches rely on the same core idea: maintain frequency of frequencies. Without this second structure, answering hasFrequency would require scanning all counts, which costs O(n). Using a secondary tracker keeps every operation constant time and fits well with design-style problems that require efficient updates and queries.
Recommended for interviews: The two-hash-map solution is what interviewers expect. It clearly demonstrates understanding of frequency counting with a hash table and how to optimize repeated queries. A naive scan would work functionally but fails the performance requirement. Showing the frequency-of-frequencies optimization signals strong problem-solving and system design thinking.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two Hash Maps (Number Count + Frequency Count) | O(1) per operation | O(n) | General case; best interview solution with constant-time updates and queries |
| List + Frequency Counter | O(1) average per operation | O(n) | When number range is bounded and array indexing is faster than hash lookups |