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.The key idea behind solving #2671 Frequency Tracker is to efficiently maintain counts of numbers and quickly determine whether any number appears a specific number of times. A naive solution would recompute frequencies each time, but that would be too slow for frequent updates.
A more optimal design uses two hash tables. The first map stores the frequency of each number (num → freq). The second map keeps track of how many numbers currently have a certain frequency (freq → count). Whenever an element is added or removed, both structures are updated accordingly. This allows the system to instantly check whether any number has a given frequency.
By maintaining these synchronized maps, the operations for adding a number, deleting one occurrence, and checking a frequency can all be performed in constant time. This design-focused approach highlights efficient state tracking and is common in interview problems involving dynamic frequency updates.
Time Complexity: O(1) per operation. Space Complexity: O(n) for storing frequencies.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Map with Frequency Counter Map | O(1) per operation (add, deleteOne, hasFrequency) | O(n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Put all the numbers in a hash map (or just an integer array given the number range is small) to maintain each number’s frequency dynamically.
Put each frequency in another hash map (or just an integer array given the range is small, note there are only 200000 calls in total) to maintain each kind of frequency dynamically.
Keep the 2 hash maps in sync.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Problems like Frequency Tracker are common in coding interviews because they test hash table usage and system design thinking. Variations involving frequency counting and efficient updates frequently appear in FAANG-style interview rounds.
Hash tables are the most suitable data structures for this problem. They allow efficient updates and lookups when maintaining number frequencies and tracking how many numbers share the same frequency.
One hash map tracks the frequency of each number, while the second tracks how many numbers exist with a given frequency. This dual structure enables constant-time checks when verifying if a certain frequency exists.
The optimal approach uses two hash maps: one to store the frequency of each number and another to track how many numbers have a particular frequency. This structure allows constant-time updates and quick checks for whether any number matches a requested frequency.