Frequency Tracker

Medium

Asked by:

1 view

Topics:

Arrays

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.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the input numbers to be added/deleted, as well as the frequency to check?
How many add, deleteOne, and hasFrequency operations can we expect to perform in total?
If I try to delete a number that doesn't exist in the tracker, should I do nothing, or should I return an error?
If multiple numbers have the same target frequency in `hasFrequency(frequency)`, do I only need to find one, or do I need to return all of them (if so, how would you like that returned)?
What data type should I use for storing the counts and frequencies (e.g., integer, long)? Are there any memory limitations I should be aware of?

Brute Force Solution

Approach

The brute force approach for frequency tracking means we'll directly simulate each operation and see if it leads to the desired outcome. We will build up a representation of the numbers stored and then perform operations to track the frequencies.

Here's how the algorithm would work step-by-step:

Keep track of the numbers that are added to our collection.
For the 'add' operation, simply put that number into our collection.
For the 'delete' operation, look through the collection for that number and if found, remove it.
For the 'check' operation, count how many times that frequency has appeared amongst the numbers in our collection.
If that frequency has appeared, return 'true', otherwise return 'false'.

Code Implementation

class FrequencyTracker:
    def __init__(self):
        self.data_storage = []

    def add(self, number):
        self.data_storage.append(number)
        self.recount_frequencies()

    def deleteOne(self, number):
        try:
            self.data_storage.remove(number)
        except ValueError:
            pass
        self.recount_frequencies()

    def hasFrequency(self, frequency):
        # Recounting frequencies is essential before checking.
        frequencies = self.recount_frequencies()

        for number_frequency in frequencies.values():
            if number_frequency == frequency:
                return True

        return False

    def recount_frequencies(self):
        #  Frequencies must be counted to maintain data integrity
        frequencies = {}

        for number in self.data_storage:
            if number in frequencies:
                frequencies[number] += 1
            else:
                frequencies[number] = 1

        return frequencies

Big(O) Analysis

Time Complexity

O(n) – The 'add' operation takes O(1) time as it's a simple insertion into a collection. The 'delete' operation requires searching the collection, which in the worst case (element not found or at the end) takes O(n) time. The 'check' operation iterates through the entire collection to count the frequency of frequencies, also taking O(n) time. Therefore, considering a single operation, the dominant operation is O(n).

Space Complexity

O(N) – The brute force approach keeps track of the numbers added to the collection, effectively creating a list (or similar data structure) to store these numbers. In the worst case, all 'add' operations could add unique numbers, meaning the list would grow linearly with the number of 'add' operations. Therefore, the auxiliary space used to store these numbers grows proportionally to N, where N is the total number of 'add' operations. This results in a space complexity of O(N).

Optimal Solution

Approach

To efficiently track the frequency of numbers and determine if certain frequencies exist, we use a strategic data storage method. Instead of searching through all numbers repeatedly, we'll use clever ways to remember how many times each number appears and how many numbers have specific counts.

Here's how the algorithm would work step-by-step:

We'll use one system to quickly find out how many times a number has appeared.
We'll use a second system to keep track of how many numbers have a certain count (e.g., how many numbers appear exactly twice).
When we add a number, we first update its count in the first system.
Then, we update the second system to reflect that the old count is now one less frequent, and the new count is one more frequent.
When we remove a number, we do almost the same thing: update the first system, then update the second system to reflect the changes in counts.
To check if a certain frequency exists, we simply look it up in the second system. If the count for that frequency is greater than zero, then it exists.

Code Implementation

class FrequencyTracker:

    def __init__(self):
        self.number_counts = {}
        self.frequency_counts = {}

    def add(self, number):
        if number in self.number_counts:
            old_frequency = self.number_counts[number]
            self.number_counts[number] += 1
            new_frequency = self.number_counts[number]
            self.frequency_counts[old_frequency] -= 1
            if self.frequency_counts[old_frequency] == 0:
                del self.frequency_counts[old_frequency]
            if new_frequency not in self.frequency_counts:
                self.frequency_counts[new_frequency] = 0
            self.frequency_counts[new_frequency] += 1
        else:
            self.number_counts[number] = 1
            if 1 not in self.frequency_counts:
                self.frequency_counts[1] = 0
            self.frequency_counts[1] += 1

    def deleteOne(self, number):
        if number in self.number_counts:
            current_frequency = self.number_counts[number]

            # Handle deletion only if the number exists
            self.frequency_counts[current_frequency] -= 1
            if self.frequency_counts[current_frequency] == 0:
                del self.frequency_counts[current_frequency]
            
            if self.number_counts[number] == 1:
                del self.number_counts[number]
            else:
                self.number_counts[number] -= 1

                new_frequency = self.number_counts[number]

                # Update frequency counts after decrement
                if new_frequency not in self.frequency_counts:
                    self.frequency_counts[new_frequency] = 0
                self.frequency_counts[new_frequency] += 1

    def hasFrequency(self, frequency):
        # Check to see if the frequency exists
        if frequency in self.frequency_counts:
            if self.frequency_counts[frequency] > 0:
                return True
        return False

Big(O) Analysis

Time Complexity

O(1) – The frequency tracker uses two hash maps (or dictionaries). The first hash map stores the frequency of each number, and the second stores the count of each frequency. Adding, deleting, or checking for the existence of a frequency involves only hash map lookups and updates. Since hash map operations (get and put) have an average time complexity of O(1), each operation takes constant time regardless of the number of elements stored.

Space Complexity

O(N) – The solution uses two data structures: one to store the frequency of each number, and another to track the number of times each frequency occurs. The first data structure, which stores counts for each number, could potentially store a count for every unique number in the input. If the input contains N unique numbers, this first data structure will use O(N) space. The second data structure, tracking frequency counts, could potentially need to store counts for each possible frequency, which in the worst case could also be up to N (if each number appears only once). Therefore, the overall auxiliary space complexity is O(N) + O(N), which simplifies to O(N).

Edge Cases

Case	How to Handle
Adding a number when the number is already present with a high frequency	The frequency count should be correctly incremented, and the old frequency's count decremented and removed if it becomes zero.
Deleting a number when it's not present in the tracker.	The deleteOne operation should do nothing and not throw an error.
Deleting a number such that its frequency becomes zero.	The number should effectively be removed from the tracker, and its previous frequency count decremented.
Calling hasFrequency with a frequency of 0.	hasFrequency(0) should return true only if there are numbers with a frequency of 0 which might happen after deleting the last occurence of a number, or false if the frequency tracker is empty.
Calling hasFrequency with a very large frequency (close to integer limit).	The solution should handle large frequencies without integer overflow or performance degradation by using appropriate data types.
Adding, deleting, and querying the same number repeatedly in a short time span.	The solution should maintain consistent frequency counts and hasFrequency results after these rapid updates.
Adding a large number of distinct elements, each appearing only once.	The solution's memory usage should scale linearly with the number of distinct elements.
Adding a negative number.	The implementation should correctly handle negative numbers as inputs to the add and deleteOne operations by not making assumptions of input bounds.

Adding a number when the number is already present with a high frequency

How to Handle:

The frequency count should be correctly incremented, and the old frequency's count decremented and removed if it becomes zero.

Deleting a number when it's not present in the tracker.

How to Handle:

The deleteOne operation should do nothing and not throw an error.

Deleting a number such that its frequency becomes zero.

How to Handle:

The number should effectively be removed from the tracker, and its previous frequency count decremented.

Calling hasFrequency with a frequency of 0.

How to Handle:

hasFrequency(0) should return true only if there are numbers with a frequency of 0 which might happen after deleting the last occurence of a number, or false if the frequency tracker is empty.

Calling hasFrequency with a very large frequency (close to integer limit).

How to Handle:

The solution should handle large frequencies without integer overflow or performance degradation by using appropriate data types.

Adding, deleting, and querying the same number repeatedly in a short time span.

How to Handle:

The solution should maintain consistent frequency counts and hasFrequency results after these rapid updates.

Adding a large number of distinct elements, each appearing only once.

How to Handle:

The solution's memory usage should scale linearly with the number of distinct elements.

Adding a negative number.

How to Handle:

The implementation should correctly handle negative numbers as inputs to the add and deleteOne operations by not making assumptions of input bounds.