Frequency Tracker - Solution & Explanation

Problem Statement

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.

Approach Overview

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 1: Using Two Hash Maps

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.

Code

Python JavaScript

Python

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Using a List and Counter

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.

Code

C++Java

C++

Java

Complexity

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.

Try this approach in the editor →

Approach 3: 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.

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.

Code

Python Java C++Go TypeScript Rust

Python

Java

C++

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Using Two Hash Maps	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.
Using a List and Counter	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.
Hash Table	—

Detailed Complexity Analysis

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

Video Solution

Leetcode 2671 Frequency Tracker • ThinkCode • 646 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Frequency Tracker with our built-in code editor and test cases.

Practice on FleetCode

Two Sum

Longest Substring Without Repeating Characters

Problem Info

DifficultyMedium

Acceptance31.6%

Approaches3

Reading time14 min

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Using Two Hash Maps

Code

Complexity

Approach 2: Using a List and Counter

Code

Complexity

Approach 3: Hash Table

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents