Is Frequency Tracker easy or hard?

Frequency Tracker is considered a medium difficulty problem on LeetCode. The operations themselves are simple, but the challenge is recognizing that a second map tracking frequency counts is required to answer queries in constant time.

Frequency Tracker Python/Java solution

In Python or JavaScript, the typical implementation uses two dictionaries (hash maps). In Java or C++, developers often use HashMap or unordered_map along with an auxiliary frequency counter or array. The algorithmic idea remains the same regardless of language.

How to solve Frequency Tracker in O(n)?

The overall structure stores up to n distinct numbers, so space grows to O(n). Each operation itself runs in O(1) time by updating two structures: the count of each number and the number of elements that have a given frequency. Checking hasFrequency(f) simply verifies whether the frequency counter for f is greater than zero.

What is the best approach for Frequency Tracker?

The best approach uses two hash maps: one mapping numbers to their counts and another mapping frequencies to how many numbers have that frequency. This allows add, delete, and frequency queries to run in O(1) time. The key trick is maintaining a "frequency of frequencies" structure so hasFrequency() becomes a constant-time lookup.

Is Frequency Tracker asked at Google/Amazon/Meta?

Frequency-tracking design problems frequently appear in interviews at large tech companies because they test hash map reasoning and data structure design. Variants of this problem or similar frequency counting tasks have appeared in interviews at companies like Amazon and Meta, especially in mid-level backend or systems interviews.

What data structure is used in Frequency Tracker?

The core data structures are hash tables. One hash table tracks how many times each number appears, while another tracks how many numbers currently have a specific frequency. Some implementations replace the first hash map with an array when the value range is bounded.

What is the time complexity of Frequency Tracker?

With the optimal design, each operation—add, deleteOne, and hasFrequency—runs in O(1) time on average. The data structure uses hash map updates and lookups, which are constant time in typical implementations. Space complexity is O(n) where n is the number of distinct values stored.

Description Hints 3 Solution Video 8:58

2671. Frequency Tracker

Medium31.6% acceptance

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 <= 10⁵
1 <= frequency <= 10⁵
At most, 2 * 10⁵ calls will be made to add, deleteOne, and hasFrequency in total.

Topics

Design Hash Table

Hints open one at a time

Hint 1

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.

Hint 2

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.

Hint 3

Keep the 2 hash maps in sync.

8:58

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class FrequencyTracker:

  def __init__(self):
      

  def add(self, number: int) -> None:
      

  def deleteOne(self, number: int) -> None:
      

  def hasFrequency(self, frequency: int) -> bool:
      


16# Your FrequencyTracker object will be instantiated and called as such:
17# obj = FrequencyTracker()
18# obj.add(number)
19# obj.deleteOne(number)
20# param_3 = obj.hasFrequency(frequency)

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

["FrequencyTracker","add","add","hasFrequency"]
[[],[3],[3],[2]]

Input

["FrequencyTracker","add","deleteOne","hasFrequency"]
[[],[1],[1],[1]]

Input

["FrequencyTracker","hasFrequency","add","hasFrequency"]
[[],[2],[3],[1]]

Your code is saved on this device.Solution