LeetCode Solutions Blog

Frequency Tracker

Number: 2778

Difficulty: Medium

Paid? No

Companies: Microsoft

Problem Description

Design a data structure that tracks integer values and supports three operations: adding a number, deleting one occurrence of a number, and checking if any number appears exactly a given number of times.

Key Insights

Use one map (or dictionary) to keep track of the count for each number.
Use a second map to maintain how many numbers have a specific frequency.
When updating a number's count, update both maps to reflect changes in frequency.
The hasFrequency query can be answered in O(1) time by inspecting the frequency map.

Space and Time Complexity

Time Complexity: O(1) per operation. Space Complexity: O(n), where n is the number of unique numbers stored.

Solution

To efficiently support the operations, maintain two maps: one mapping a number to its current count and another mapping a frequency to the number of elements with that frequency. In the add operation, increment the count for the number and update the frequency map by decrementing the old frequency and incrementing the new frequency. In the deleteOne operation, check if the number exists, then decrement its count along with proper updates to the frequency map. Finally, hasFrequency simply checks if there exists any number with the specified frequency using the frequency map.

Code Solutions

# Python solution for Frequency Tracker

class FrequencyTracker:
    def __init__(self):
        # num_count stores the frequency for each number
        self.num_count = {}
        # freq_count stores the count of numbers that have a given frequency
        self.freq_count = {}

    def add(self, number: int) -> None:
        # Get the current frequency of the number (default 0)
        old_freq = self.num_count.get(number, 0)
        new_freq = old_freq + 1
        # Update the count for the number
        self.num_count[number] = new_freq
        # Decrement the count of numbers with the old frequency
        if old_freq > 0:
            self.freq_count[old_freq] -= 1
        # Increment the count of numbers with the new frequency
        self.freq_count[new_freq] = self.freq_count.get(new_freq, 0) + 1

    def deleteOne(self, number: int) -> None:
        # Only delete if the number exists and has a count greater than 0
        if number in self.num_count and self.num_count[number] > 0:
            old_freq = self.num_count[number]
            new_freq = old_freq - 1
            # Update the count for the number
            self.num_count[number] = new_freq
            # Decrement the frequency count for the old frequency
            self.freq_count[old_freq] -= 1
            # If the number still exists (new_freq > 0), update freq_count map
            if new_freq > 0:
                self.freq_count[new_freq] = self.freq_count.get(new_freq, 0) + 1

    def hasFrequency(self, frequency: int) -> bool:
        # Return true if there is any number with exactly 'frequency' occurrences
        return self.freq_count.get(frequency, 0) > 0