LeetCode 2671 - Frequency Tracker

LeetCode Problem 2671

Difficulty: 🟡 Medium
Topics: Hash Table, Design

Solution

Problem Understanding

The problem asks us to design a data structure, FrequencyTracker, that can efficiently track the frequency of numbers and answer queries about whether any number exists with a specific frequency. The operations are add, which increases the count of a number; deleteOne, which decreases the count of a number if it exists; and hasFrequency, which checks whether any number occurs exactly frequency times.

The input represents integers in the range 1 <= number <= 10^5 added or removed from the data structure, and queries hasFrequency for 1 <= frequency <= 10^5. The total number of operations is limited to 2 * 10^5, so an efficient solution is required to avoid timeouts.

Important edge cases include checking hasFrequency on an empty structure, deleting a number that does not exist, and handling multiple numbers with the same frequency. A naive solution that scans the entire dataset for each query would be too slow because it could lead to O(n) time per query, where n is the number of elements.

Approaches

The brute-force approach involves maintaining a list of all numbers and iterating through it to calculate frequencies each time hasFrequency is called. This is correct but inefficient because hasFrequency could take O(n) time per query, making it unacceptable for large inputs.

The optimal approach uses two hash maps. The first map tracks the count of each number (number -> count). The second map tracks how many numbers have a specific count (count -> number of numbers with this count). This allows add and deleteOne to update both maps in O(1) time and hasFrequency to check in O(1) whether any number has the queried frequency.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n) per query	O(n)	Maintain a list and compute frequencies on demand
Optimal	O(1) per operation	O(n)	Use two hash maps to track counts and frequencies

Algorithm Walkthrough

1. Initialize two hash maps: count_map for storing the frequency of each number and freq_map for storing how many numbers have a given frequency.
2. Add(number):

• Retrieve the current count of the number from count_map.
• If the number already exists, decrement its old frequency in freq_map.
• Increment the number's count in count_map.
• Increment the new frequency in freq_map.

3. DeleteOne(number):

• Check if the number exists in count_map. If it does not, do nothing.
• Retrieve the current count and decrement the corresponding frequency in freq_map.
• Decrement the number's count in count_map.
• If the new count is greater than zero, increment the new frequency in freq_map.
• If the count becomes zero, remove the number from count_map.

4. HasFrequency(frequency):

• Simply check if freq_map[frequency] > 0.

Why it works: The count_map always reflects the current count of each number, and freq_map tracks the count of numbers having a particular frequency. This ensures that hasFrequency queries are accurate and O(1), while updates maintain both maps consistently.

Python Solution

class FrequencyTracker:

    def __init__(self):
        self.count_map = {}
        self.freq_map = {}

    def add(self, number: int) -> None:
        current_count = self.count_map.get(number, 0)
        if current_count > 0:
            self.freq_map[current_count] -= 1
        new_count = current_count + 1
        self.count_map[number] = new_count
        self.freq_map[new_count] = self.freq_map.get(new_count, 0) + 1

    def deleteOne(self, number: int) -> None:
        if number not in self.count_map:
            return
        current_count = self.count_map[number]
        self.freq_map[current_count] -= 1
        new_count = current_count - 1
        if new_count > 0:
            self.count_map[number] = new_count
            self.freq_map[new_count] = self.freq_map.get(new_count, 0) + 1
        else:
            del self.count_map[number]

    def hasFrequency(self, frequency: int) -> bool:
        return self.freq_map.get(frequency, 0) > 0

This implementation ensures all operations are O(1) by maintaining two synchronized hash maps. Adding or deleting a number updates both maps accordingly, while querying a frequency simply checks the frequency map.

Go Solution

type FrequencyTracker struct {
	countMap map[int]int
	freqMap  map[int]int
}

func Constructor() FrequencyTracker {
	return FrequencyTracker{
		countMap: make(map[int]int),
		freqMap:  make(map[int]int),
	}
}

func (this *FrequencyTracker) Add(number int) {
	currentCount := this.countMap[number]
	if currentCount > 0 {
		this.freqMap[currentCount]--
	}
	newCount := currentCount + 1
	this.countMap[number] = newCount
	this.freqMap[newCount]++
}

func (this *FrequencyTracker) DeleteOne(number int) {
	currentCount, exists := this.countMap[number]
	if !exists {
		return
	}
	this.freqMap[currentCount]--
	newCount := currentCount - 1
	if newCount > 0 {
		this.countMap[number] = newCount
		this.freqMap[newCount]++
	} else {
		delete(this.countMap, number)
	}
}

func (this *FrequencyTracker) HasFrequency(frequency int) bool {
	return this.freqMap[frequency] > 0
}

Go implementation mirrors the Python logic, using maps instead of dictionaries and handling deletion with the built-in delete function.

Worked Examples

Example 1:

Operation	count_map	freq_map	Output
add(3)	{3:1}	{1:1}	null
add(3)	{3:2}	{1:0, 2:1}	null
hasFrequency(2)	{3:2}	{1:0, 2:1}	true

Example 2:

Operation	count_map	freq_map	Output
add(1)	{1:1}	{1:1}	null
deleteOne(1)	{}	{1:0}	null
hasFrequency(1)	{}	{1:0}	false

Example 3:

Operation	count_map	freq_map	Output
hasFrequency(2)	{}	{}	false
add(3)	{3:1}	{1:1}	null
hasFrequency(1)	{3:1}	{1:1}	true

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1) per operation	Each operation performs a constant number of hash map accesses and updates
Space	O(n)	Two hash maps store counts of all numbers and frequencies; n is the number of distinct numbers

The O(1) time is guaranteed because we do not iterate over all numbers or frequencies for any operation. The space is proportional to the number of distinct elements and frequencies encountered.

Test Cases

# Provided examples
obj = FrequencyTracker()
obj.add(3)
obj.add(3)
assert obj.hasFrequency(2) == True  # Example 1

obj = FrequencyTracker()
obj.add(1)
obj.deleteOne(1)
assert obj.hasFrequency(1) == False  # Example 2

obj = FrequencyTracker()
assert obj.hasFrequency(2) == False
obj.add(3)
assert obj.hasFrequency(1) == True  # Example 3

# Edge cases
obj = FrequencyTracker()
assert obj.hasFrequency(1) == False  # Empty structure
obj.add(2)
obj.add(2)
obj.add(3)
assert obj.hasFrequency(2) == True
obj.deleteOne(2)
assert obj.hasFrequency(2) == False
obj.deleteOne(2)
assert obj.hasFrequency(1) == True

Test	Why
Example 1	Tests multiple adds of the same number
Example 2	Tests deleteOne leading to empty structure
Example 3	Tests hasFrequency on empty then after add
Edge case empty	Tests hasFrequency returns False on empty structure
Mixed adds/deletes	Validates that frequency tracking updates correctly

Edge Cases

The first edge case is querying hasFrequency on an empty FrequencyTracker. This could trip up naive implementations if they assume at least one element exists. Our implementation handles it by returning False because the freq_map does not contain any counts.

The second edge case involves deleting a number that does not exist in the structure. A naive implementation might throw an error or decrement an undefined count. In our solution, we check for existence before performing any deletion, ensuring stability.

The third edge case is having multiple numbers with the same frequency. For example, two numbers might each occur three times, and deleting one occurrence from one of them reduces the count of that frequency but does not remove it entirely. Our freq_map tracks the number of numbers with a