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.
Using two hash maps: One will map numbers to their frequencies, and another will map frequencies to the count of numbers having that frequency. This allows for efficient updates and queries regarding frequencies.
This implementation uses a dictionary num_count to keep track of the number of times each number occurs, and another dictionary freq_count to track the number of numbers that have a particular frequency. When we add or delete a number, we update both dictionaries to maintain consistency.
Python
JavaScript
Time Complexity: O(1) for add, deleteOne, and hasFrequency operations.
Space Complexity: O(n), where n is the number of distinct numbers in the data structure.
Alternatively, we can use a list to keep track of the elements and a counter to record the frequency of each element. This approach is less efficient but conceptually simpler for certain operations.
In this C++ implementation, we use unordered_map to maintain the count of each number and the count of numbers with certain frequencies. This allows the operations to run efficiently, similar to the Python solution.
Time Complexity: O(1) for add, deleteOne, and hasFrequency operations.
Space Complexity: O(n), where n is the number of distinct numbers in the data structure.
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.
For the add operation, we directly decrement the value corresponding to cnt[number] in the hash table freq, then increment cnt[number], and finally increment the value corresponding to cnt[number] in freq.
For the deleteOne operation, we first check if cnt[number] is greater than zero. If it is, we decrement the value corresponding to cnt[number] in the hash table freq, then decrement cnt[number], and finally increment the value corresponding to cnt[number] in freq.
For the hasFrequency operation, we directly return whether freq[frequency] is greater than zero.
In terms of time complexity, since we use hash tables, the time complexity of each operation is O(1). The space complexity is O(n), where n is the number of distinct numbers.
| Approach | Complexity |
|---|---|
| Using Two Hash Maps | Time Complexity: O(1) for add, deleteOne, and hasFrequency operations. |
| Using a List and Counter | Time Complexity: O(1) for add, deleteOne, and hasFrequency operations. |
| Hash Table | — |
| 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 |
Leetcode 2671 Frequency Tracker • ThinkCode • 639 views views
Watch 9 more video solutions →Practice Frequency Tracker with our built-in code editor and test cases.
Practice on FleetCode