# LC 2671. Frequency Tracker

### [Problem link](https://leetcode.com/problems/frequency-tracker/)

###### tags: `leedcode` `python` `medium`

Design a data structure that keeps track of the values in it and answers some queries regarding their frequencies.

Implement the <code>FrequencyTracker</code> class.

- <code>FrequencyTracker()</code>: Initializes the <code>FrequencyTracker</code> object with an empty array initially.
- <code>void add(int number)</code>: Adds <code>number</code> to the data structure.
- <code>void deleteOne(int number)</code>: Deletes **one** occurrence of <code>number</code> from the data structure. The data structure **may not contain** <code>number</code>, and in this case nothing is deleted.
- <code>bool hasFrequency(int frequency)</code>: Returns <code>true</code> if there is a number in the data structure that occurs <code>frequency</code> number of times, otherwise, it returns <code>false</code>.

**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:**

- <code>1 <= number <= 10⁵</code>
- <code>1 <= frequency <= 10⁵</code>
- At most, <code>2 *10⁵</code>calls will be made to <code>add</code>, <code>deleteOne</code>, and <code>hasFrequency</code>in **total** .

## Solution 1

class FrequencyTracker:

    def __init__(self):
        self.num = defaultdict(int) # number, count
        self.frequency = defaultdict(list) # freq, number

    def add(self, number: int) -> None:
        if self.num[number] > 0:
            self.frequency[self.num[number]].remove(number)
            self.num[number] += 1
            self.frequency[self.num[number]].append(number)
        else:
            self.num[number] += 1
            self.frequency[1].append(number)

    def deleteOne(self, number: int) -> None:
        if self.num[number] > 0:
            self.frequency[self.num[number]].remove(number)
            self.num[number] -= 1
            if self.num[number] >= 1:
                self.frequency[self.num[number]].append(number)

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


# Your FrequencyTracker object will be instantiated and called as such:
# obj = FrequencyTracker()
# obj.add(number)
# obj.deleteOne(number)
# param_3 = obj.hasFrequency(frequency)

>### Complexity
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(n) | O(n) |

## Note
x