LeetCode Solutions Blog

Frequency Tracker

Difficulty: Medium

Problem Description

Design a data structure that keeps track of the values in it and answers some queries regarding their frequencies. Implement the FrequencyTracker class with the following methods:

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.

Key Insights

We need to maintain the frequency of each number added to the data structure.
We also need to keep track of how many numbers have a specific frequency.
Efficiently manage add, delete, and frequency check operations.

Space and Time Complexity

Time Complexity:

add: O(1)
deleteOne: O(1)
hasFrequency: O(1)

Space Complexity: O(n) where n is the number of unique numbers added to the data structure.

Solution

To solve this problem, we can use two hash tables (or dictionaries):

number_count: This keeps track of how many times each number has been added.
frequency_count: This keeps track of how many numbers have a specific frequency.

The add method increments the count of the number and updates the frequency count accordingly. The deleteOne method decrements the count of the number (if it exists) and updates the frequency count. The hasFrequency method simply checks if any number has the specified frequency.

Code Solutions

class FrequencyTracker:
    def __init__(self):
        self.number_count = {}  # Dictionary to track frequency of each number
        self.frequency_count = {}  # Dictionary to track how many numbers have a specific frequency

    def add(self, number: int) -> None:
        # Update the frequency of the number
        if number in self.number_count:
            current_freq = self.number_count[number]
            self.number_count[number] += 1
            new_freq = current_freq + 1
            
            # Update frequency count
            self.frequency_count[current_freq] -= 1
            if self.frequency_count[current_freq] == 0:
                del self.frequency_count[current_freq]
            if new_freq in self.frequency_count:
                self.frequency_count[new_freq] += 1
            else:
                self.frequency_count[new_freq] = 1
        else:
            # New number, frequency is 1
            self.number_count[number] = 1
            if 1 in self.frequency_count:
                self.frequency_count[1] += 1
            else:
                self.frequency_count[1] = 1

    def deleteOne(self, number: int) -> None:
        # Decrease the frequency of the number
        if number in self.number_count and self.number_count[number] > 0:
            current_freq = self.number_count[number]
            self.number_count[number] -= 1
            new_freq = current_freq - 1
            
            # Update frequency count
            self.frequency_count[current_freq] -= 1
            if self.frequency_count[current_freq] == 0:
                del self.frequency_count[current_freq]
            if new_freq > 0:
                if new_freq in self.frequency_count:
                    self.frequency_count[new_freq] += 1
                else:
                    self.frequency_count[new_freq] = 1

    def hasFrequency(self, frequency: int) -> bool:
        # Check if a number exists with the given frequency
        return frequency in self.frequency_count