Problem Description

You need to design a data structure that tracks numbers and can answer queries about how frequently numbers appear.

The FrequencyTracker class should support the following operations:

1. FrequencyTracker(): Creates a new frequency tracker that starts with no numbers stored.

2. add(int number): Adds one occurrence of number to the data structure. If the number already exists, its count increases by one.

3. deleteOne(int number): Removes one occurrence of number from the data structure. If the number doesn't exist or has zero occurrences, nothing happens.

4. hasFrequency(int frequency): Checks if there's at least one number in the data structure that appears exactly frequency times. Returns true if such a number exists, false otherwise.

The key challenge is to efficiently track both the count of each number and how many numbers have each specific frequency. The solution uses two hash tables:

• cnt: Maps each number to its occurrence count
• freq: Maps each frequency value to how many numbers have that frequency

When adding a number, the solution updates both hash tables - it decreases the count of numbers with the old frequency, increases the number's count, then increases the count of numbers with the new frequency.

Similarly, when deleting, it first checks if the number exists (count > 0), then updates both hash tables to reflect the frequency change.

The hasFrequency operation simply checks if any numbers have the requested frequency by looking up freq[frequency].

Intuition

The straightforward approach would be to use a single hash table to count occurrences of each number. However, this makes the hasFrequency operation inefficient - we'd need to iterate through all numbers to check if any has the target frequency, resulting in O(n) time complexity.

The key insight is that we need to answer frequency queries quickly. Instead of searching for a frequency when asked, we can maintain this information as we modify the data structure. This leads us to think: what if we track the frequencies themselves?

Consider what happens when we add a number:

• If a number appears 2 times and we add it again, it now appears 3 times
• This means one less number has frequency 2, and one more number has frequency 3
• The frequency distribution changes with each operation

This observation suggests we need a second hash table that answers: "How many numbers have frequency X?" By maintaining this information during add/delete operations, we can answer hasFrequency queries in O(1) time.

The tricky part is keeping both hash tables synchronized. When we modify a number's count from old_count to new_count:

1. We decrease freq[old_count] by 1 (one less number has the old frequency)
2. We increase freq[new_count] by 1 (one more number has the new frequency)

This dual hash table approach trades a bit of extra space and update complexity for constant-time frequency queries, making all operations O(1) on average.

Solution Approach

The solution uses two hash tables to efficiently track both the count of each number and the frequency distribution:

1. cnt: A dictionary that maps each number to its occurrence count
2. freq: A dictionary that maps each frequency value to how many numbers have that frequency

Let's walk through each operation:

Initialization

def __init__(self):
    self.cnt = defaultdict(int)
    self.freq = defaultdict(int)

Both hash tables are initialized as defaultdict(int) which returns 0 for missing keys, simplifying our code by avoiding key existence checks.

Add Operation

def add(self, number: int) -> None:
    self.freq[self.cnt[number]] -= 1
    self.cnt[number] += 1
    self.freq[self.cnt[number]] += 1

When adding a number:

1. First, decrease the count of numbers having the current frequency: self.freq[self.cnt[number]] -= 1
2. Increment the number's count: self.cnt[number] += 1
3. Increase the count of numbers having the new frequency: self.freq[self.cnt[number]] += 1

For example, if number 5 appears twice (cnt[5] = 2), after adding it:

• Decrease freq[2] by 1 (one less number appears exactly twice)
• Update cnt[5] to 3
• Increase freq[3] by 1 (one more number appears exactly three times)

Delete Operation

def deleteOne(self, number: int) -> None:
    if self.cnt[number]:
        self.freq[self.cnt[number]] -= 1
        self.cnt[number] -= 1
        self.freq[self.cnt[number]] += 1

The deletion follows similar logic but first checks if the number exists (self.cnt[number] > 0):

1. Decrease the count of numbers with the current frequency
2. Decrement the number's count
3. Increase the count of numbers with the new frequency

Note that when a number's count becomes 0, we still track it in freq[0], which doesn't affect our hasFrequency queries since frequency queries are for positive values.

HasFrequency Operation

def hasFrequency(self, frequency: int) -> bool:
    return self.freq[frequency] > 0

This simply checks if any numbers have the specified frequency by looking up freq[frequency]. If the value is greater than 0, at least one number has that frequency.

The time complexity for all operations is O(1) on average due to hash table operations. The space complexity is O(n) where n is the number of unique numbers stored.

Example Walkthrough

Let's trace through a sequence of operations to see how both hash tables work together:

Initial state:

• cnt = {} (tracks number → count)
• freq = {} (tracks frequency → how many numbers have that frequency)

Operation 1: add(3)

• Before: cnt[3] = 0, so freq[0] -= 1 → freq[0] = -1
• Update: cnt[3] = 1
• After: freq[1] += 1 → freq[1] = 1
• State: cnt = {3: 1}, freq = {0: -1, 1: 1}

Operation 2: add(3)

• Before: cnt[3] = 1, so freq[1] -= 1 → freq[1] = 0
• Update: cnt[3] = 2
• After: freq[2] += 1 → freq[2] = 1
• State: cnt = {3: 2}, freq = {0: -1, 1: 0, 2: 1}

Operation 3: add(5)

• Before: cnt[5] = 0, so freq[0] -= 1 → freq[0] = -2
• Update: cnt[5] = 1
• After: freq[1] += 1 → freq[1] = 1
• State: cnt = {3: 2, 5: 1}, freq = {0: -2, 1: 1, 2: 1}

Operation 4: hasFrequency(2)

• Check: freq[2] > 0 → 1 > 0 → returns true
• (Number 3 appears exactly 2 times)

Operation 5: hasFrequency(1)

• Check: freq[1] > 0 → 1 > 0 → returns true
• (Number 5 appears exactly 1 time)

Operation 6: deleteOne(3)

• Check: cnt[3] = 2 > 0, proceed with deletion
• Before: freq[2] -= 1 → freq[2] = 0
• Update: cnt[3] = 1
• After: freq[1] += 1 → freq[1] = 2
• State: cnt = {3: 1, 5: 1}, freq = {0: -2, 1: 2, 2: 0}

Operation 7: hasFrequency(2)

• Check: freq[2] > 0 → 0 > 0 → returns false
• (No number appears exactly 2 times anymore)

Operation 8: hasFrequency(1)

• Check: freq[1] > 0 → 2 > 0 → returns true
• (Both numbers 3 and 5 appear exactly 1 time each)

Notice how the freq table maintains accurate counts of how many numbers have each frequency, enabling O(1) frequency queries. The negative values in freq[0] don't affect our queries since we only check positive frequencies.

Solution Implementation

Time and Space Complexity

Time Complexity: Each operation (add, deleteOne, and hasFrequency) has a time complexity of O(1).

• The add method performs three dictionary operations: one read from self.cnt[number], and three updates to self.freq and self.cnt. All dictionary operations in Python using hash tables have average O(1) time complexity.

• The deleteOne method first checks if the number exists (O(1)), then performs similar dictionary operations as add if the condition is met. All operations are O(1).

• The hasFrequency method simply performs a dictionary lookup and comparison, which is O(1).

Space Complexity: The space complexity is O(n), where n is the number of distinct numbers added to the tracker.

• The self.cnt dictionary stores at most n distinct numbers as keys with their counts as values.

• The self.freq dictionary stores frequency counts as keys. In the worst case, when all numbers have different frequencies, this could also store up to n entries. However, the number of distinct frequencies is bounded by the total number of distinct numbers.

• Therefore, the total space used is proportional to the number of distinct numbers, giving us O(n) space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Update Frequency Count Before Modifying Number Count

A critical pitfall is updating the number count before adjusting the frequency count, which leads to incorrect frequency tracking.

Incorrect Implementation:

def add(self, number: int) -> None:
    # WRONG: Incrementing count first
    self.cnt[number] += 1
    self.freq[self.cnt[number]] -= 1  # This uses the NEW count, not the old one!
    self.freq[self.cnt[number]] += 1  # This would increment the same frequency

This bug occurs because after incrementing cnt[number], we lose track of the old frequency. The operation freq[cnt[number]] -= 1 would incorrectly decrement the NEW frequency instead of the OLD frequency.

Correct Approach:

def add(self, number: int) -> None:
    # Update frequency count BEFORE changing the number count
    self.freq[self.cnt[number]] -= 1  # Uses old count
    self.cnt[number] += 1              # Now update the count
    self.freq[self.cnt[number]] += 1  # Uses new count

2. Not Checking for Existence Before Deletion

Another common mistake is forgetting to check if a number exists before attempting to delete it.

Incorrect Implementation:

def deleteOne(self, number: int) -> None:
    # WRONG: No existence check
    self.freq[self.cnt[number]] -= 1
    self.cnt[number] -= 1
    self.freq[self.cnt[number]] += 1

This would incorrectly modify frequency counts even when the number doesn't exist (count is 0), leading to negative counts in the frequency map and corrupted state.

Correct Approach:

def deleteOne(self, number: int) -> None:
    if self.cnt[number] > 0:  # Check existence first
        self.freq[self.cnt[number]] -= 1
        self.cnt[number] -= 1
        self.freq[self.cnt[number]] += 1

3. Using Regular Dictionaries Instead of DefaultDict

Using regular dictionaries requires explicit key existence checks, making the code more verbose and error-prone.

Error-Prone Implementation:

def add(self, number: int) -> None:
    # Need to check if keys exist
    if number not in self.cnt:
        self.cnt[number] = 0
    if self.cnt[number] not in self.freq:
        self.freq[self.cnt[number]] = 0
  
    self.freq[self.cnt[number]] -= 1
    self.cnt[number] += 1
  
    if self.cnt[number] not in self.freq:
        self.freq[self.cnt[number]] = 0
    self.freq[self.cnt[number]] += 1

Better Solution: Using defaultdict(int) automatically handles missing keys by returning 0, making the code cleaner and less error-prone.

4. Not Handling Frequency of Zero

Some implementations might try to "clean up" by removing entries when frequency becomes 0, but this adds unnecessary complexity.

Overly Complex:

def deleteOne(self, number: int) -> None:
    if self.cnt[number] > 0:
        self.freq[self.cnt[number]] -= 1
        if self.freq[self.cnt[number]] == 0:
            del self.freq[self.cnt[number]]  # Unnecessary cleanup
      
        self.cnt[number] -= 1
        if self.cnt[number] == 0:
            del self.cnt[number]  # Unnecessary cleanup
        else:
            self.freq[self.cnt[number]] += 1

Simpler Solution: Let the defaultdict handle zero values naturally. Since hasFrequency only checks positive frequencies, having freq[0] entries doesn't affect correctness and keeps the code simpler.