# Frequency Tracker
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/frequency-tracker)
Canonical: https://scaleengineer.com/dsa/problems/frequency-tracker
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design)
**Data structures:** Hash Table
---
## Problem
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 <= 105`
* `1 <= frequency <= 105`
* At most, `2 * 105` calls will be made to `add`, `deleteOne`, and `hasFrequency` in **total**.

# Approaches
## Brute Force using a List
This naive approach uses a simple list to store all the numbers as they are added. While `add` is simple, `deleteOne` and `hasFrequency` are inefficient as they require scanning the list.
**Time:** `add`: O(1) amortized.
`deleteOne`: O(N), where N is the total number of elements.
`hasFrequency`: O(N), as it requires a full scan of the list. · **Space:** O(N), to store all the numbers in the list, where N is the total number of elements.
**Pros:** Very simple to conceptualize and implement.; Low memory overhead if the list is compact.
**Cons:** The `deleteOne` operation is slow (O(N)).; The `hasFrequency` operation is very slow (O(N)) and inefficient if called frequently.
### Explanation
In this method, we use a standard `java.util.ArrayList` to maintain the collection of numbers.

- **`add(number)`**: This operation is straightforward; we just append the new number to the end of the list. This is an O(1) amortized operation.
- **`deleteOne(number)`**: To delete a number, we must first find it in the list. The `list.remove(Object)` method performs a linear scan, resulting in O(N) time complexity, where N is the number of elements in the list.
- **`hasFrequency(frequency)`**: This is the most expensive operation. For each call, we must determine the frequency of every unique number in the current list. This can be done by using a temporary `HashMap` to build a frequency map from scratch by iterating over the entire list, and then checking if any number has the desired frequency. This also takes O(N) time.

Due to the O(N) complexity of `deleteOne` and `hasFrequency`, this approach is too slow for the given constraints and will likely result in a 'Time Limit Exceeded' error.

```java
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class FrequencyTracker {
    private List<Integer> data;

    public FrequencyTracker() {
        data = new ArrayList<>();
    }

    public void add(int number) {
        data.add(number);
    }

    public void deleteOne(int number) {
        data.remove(Integer.valueOf(number));
    }

    public boolean hasFrequency(int frequency) {
        Map<Integer, Integer> counts = new HashMap<>();
        for (int num : data) {
            counts.put(num, counts.getOrDefault(num, 0) + 1);
        }
        for (int count : counts.values()) {
            if (count == frequency) {
                return true;
            }
        }
        return false;
    }
}
```
### Algorithm
- Initialize an `ArrayList` to store numbers.
- For `add(number)`, append the number to the list.
- For `deleteOne(number)`, find and remove one instance of the number from the list.
- For `hasFrequency(frequency)`, create a temporary frequency map by iterating through the list. Then, check if any value in the map equals the target frequency.

## Using a HashMap to Track Frequencies
This approach improves performance by using a `HashMap` to keep track of the frequency of each number. This makes `add` and `deleteOne` operations efficient, but `hasFrequency` still requires iterating through the map's values.
**Time:** `add`: O(1) average.
`deleteOne`: O(1) average.
`hasFrequency`: O(U), where U is the number of unique numbers. · **Space:** O(U), to store the unique numbers and their frequencies in the hash map, where U is the number of unique elements.
**Pros:** Efficient `add` and `deleteOne` operations with O(1) average time complexity.; More space-efficient than the list approach if there are many duplicate numbers.
**Cons:** The `hasFrequency` operation is O(U), where U is the number of unique elements. This can be slow if U is large.
### Explanation
We can significantly optimize the operations by not storing the raw numbers, but their frequencies. A `HashMap<Integer, Integer>` is used to map each number to its current count.

- **`add(number)`**: We find the number in the map, increment its current frequency, and update the map. If the number isn't present, we add it with a frequency of 1. This is an O(1) average time operation.
- **`deleteOne(number)`**: We find the number in the map and decrement its frequency. If the frequency drops to zero, we remove the number from the map to save space. This is also an O(1) average time operation.
- **`hasFrequency(frequency)`**: To check if a frequency exists, we must iterate through all the values (the frequencies) in our map. If we find any frequency that matches the input, we return `true`.

This approach is much better, but the `hasFrequency` operation's performance depends on the number of unique elements in the data structure. If there are many unique numbers, this operation can still be a bottleneck.

```java
import java.util.HashMap;
import java.util.Map;

class FrequencyTracker {
    private Map<Integer, Integer> numberToFreq;

    public FrequencyTracker() {
        numberToFreq = new HashMap<>();
    }

    public void add(int number) {
        numberToFreq.put(number, numberToFreq.getOrDefault(number, 0) + 1);
    }

    public void deleteOne(int number) {
        Integer currentFreq = numberToFreq.get(number);
        if (currentFreq != null) {
            if (currentFreq == 1) {
                numberToFreq.remove(number);
            } else {
                numberToFreq.put(number, currentFreq - 1);
            }
        }
    }

    public boolean hasFrequency(int frequency) {
        for (int freq : numberToFreq.values()) {
            if (freq == frequency) {
                return true;
            }
        }
        return false;
    }
}
```
### Algorithm
- Initialize a `HashMap<Integer, Integer>` named `numberToFreq` to store number-to-frequency mappings.
- For `add(number)`, increment the count for `number` in the map.
- For `deleteOne(number)`, decrement the count for `number`. If the count becomes zero, remove the entry.
- For `hasFrequency(frequency)`, iterate through the values of the `numberToFreq` map and check if any value equals the target frequency.

## Optimal Approach with Two HashMaps
This optimal solution uses two `HashMap`s to achieve O(1) average time complexity for all three operations. The first map tracks the frequency of each number, while the second map tracks the count of numbers for each frequency. This avoids any iteration in the `hasFrequency` query.
**Time:** `add`: O(1) average.
`deleteOne`: O(1) average.
`hasFrequency`: O(1) average. · **Space:** O(U), where U is the number of unique numbers with a non-zero frequency. Both maps store at most U entries.
**Pros:** Optimal O(1) average time complexity for all operations.; Scales well with a large number of calls and unique elements.
**Cons:** More complex to implement correctly compared to simpler approaches.; Uses more memory due to the second hash map.
### Explanation
To make `hasFrequency` an O(1) operation, we need a direct way to check if a frequency exists. This can be achieved by using a second hash map.

- **Data Structures**:
  1. `numberToFreq`: A `HashMap<Integer, Integer>` that maps a number to its current frequency.
  2. `freqToCount`: A `HashMap<Integer, Integer>` that maps a frequency to the number of elements that have that frequency.

- **`add(number)`**: When a number is added, its frequency changes from `oldFreq` to `newFreq`. We must update both maps to reflect this change. We decrement the count for `oldFreq` in `freqToCount` and increment the count for `newFreq`. Then, we update the number's frequency in `numberToFreq`.
- **`deleteOne(number)`**: This is the reverse of `add`. When a number is deleted, its frequency changes from `oldFreq` to `newFreq`. We decrement the count for `oldFreq` and increment the count for `newFreq` in `freqToCount`. Then, we update `numberToFreq`.
- **`hasFrequency(frequency)`**: This becomes a simple O(1) average time lookup. We just need to check if the given `frequency` exists as a key in our `freqToCount` map and has a count greater than zero.

This two-map strategy keeps all operations efficient and is well-suited for the problem's constraints.

```java
import java.util.HashMap;
import java.util.Map;

class FrequencyTracker {
    private Map<Integer, Integer> numberToFreq;
    private Map<Integer, Integer> freqToCount;

    public FrequencyTracker() {
        numberToFreq = new HashMap<>();
        freqToCount = new HashMap<>();
    }

    public void add(int number) {
        int oldFreq = numberToFreq.getOrDefault(number, 0);
        if (oldFreq > 0) {
            freqToCount.put(oldFreq, freqToCount.get(oldFreq) - 1);
            if (freqToCount.get(oldFreq) == 0) {
                freqToCount.remove(oldFreq);
            }
        }

        int newFreq = oldFreq + 1;
        numberToFreq.put(number, newFreq);
        freqToCount.put(newFreq, freqToCount.getOrDefault(newFreq, 0) + 1);
    }

    public void deleteOne(int number) {
        int oldFreq = numberToFreq.getOrDefault(number, 0);
        if (oldFreq == 0) {
            return;
        }

        freqToCount.put(oldFreq, freqToCount.get(oldFreq) - 1);
        if (freqToCount.get(oldFreq) == 0) {
            freqToCount.remove(oldFreq);
        }

        int newFreq = oldFreq - 1;
        if (newFreq == 0) {
            numberToFreq.remove(number);
        } else {
            numberToFreq.put(number, newFreq);
            freqToCount.put(newFreq, freqToCount.getOrDefault(newFreq, 0) + 1);
        }
    }

    public boolean hasFrequency(int frequency) {
        return freqToCount.containsKey(frequency);
    }
}
```
### Algorithm
- Initialize two `HashMap`s: `numberToFreq` and `freqToCount`.
- On `add(number)` or `deleteOne(number)`:
  1. Identify the `oldFreq` and `newFreq` for the number.
  2. Decrement the count for `oldFreq` in `freqToCount`.
  3. Update the number's frequency in `numberToFreq`.
  4. Increment the count for `newFreq` in `freqToCount`.
- For `hasFrequency(frequency)`, simply check if `frequency` is a key in `freqToCount`. This is an O(1) lookup.

# Solutions
### Java

```java
class FrequencyTracker { private Map < Integer , Integer > cnt = new HashMap <>(); private Map < Integer , Integer > freq = new HashMap <>(); public FrequencyTracker () { } public void add ( int number ) { int f = cnt . getOrDefault ( number , 0 ); if ( freq . getOrDefault ( f , 0 ) > 0 ) { freq . merge ( f , - 1 , Integer: : sum ); } cnt . merge ( number , 1 , Integer: : sum ); freq . merge ( f + 1 , 1 , Integer: : sum ); } public void deleteOne ( int number ) { int f = cnt . getOrDefault ( number , 0 ); if ( f == 0 ) { return ; } freq . merge ( f , - 1 , Integer: : sum ); cnt . merge ( number , - 1 , Integer: : sum ); freq . merge ( f - 1 , 1 , Integer: : sum ); } public boolean hasFrequency ( int frequency ) { return freq . getOrDefault ( frequency , 0 ) > 0 ; } } /** * Your FrequencyTracker object will be instantiated and called as such: * FrequencyTracker obj = new FrequencyTracker(); * obj.add(number); * obj.deleteOne(number); * boolean param_3 = obj.hasFrequency(frequency); */
```

### CPP

```cpp
class FrequencyTracker { public: FrequencyTracker () { } void add ( int number ) { int f = cnt [ number ]; if ( f > 0 ) { freq [ f ] -- ; } cnt [ number ] ++ ; freq [ f + 1 ] ++ ; } void deleteOne ( int number ) { int f = cnt [ number ]; if ( f == 0 ) { return ; } freq [ f ] -- ; cnt [ number ] -- ; freq [ f - 1 ] ++ ; } bool hasFrequency ( int frequency ) { return freq [ frequency ] > 0 ; } private: unordered_map < int , int > cnt ; unordered_map < int , int > freq ; }; /** * Your FrequencyTracker object will be instantiated and called as such: * FrequencyTracker* obj = new FrequencyTracker(); * obj->add(number); * obj->deleteOne(number); * bool param_3 = obj->hasFrequency(frequency); */
```

### Python

```python
class FrequencyTracker : def __init__ ( self ): self . cnt = defaultdict ( int ) self . freq = defaultdict ( int ) def add ( self , number : int ) -> None : if self . freq [ self . cnt [ number ]] > 0 : self . freq [ self . cnt [ number ]] -= 1 self . cnt [ number ] += 1 self . freq [ self . cnt [ number ]] += 1 def deleteOne ( self , number : int ) -> None : if self . cnt [ number ] == 0 : return self . freq [ self . cnt [ number ]] -= 1 self . cnt [ number ] -= 1 self . freq [ self . cnt [ number ]] += 1 def hasFrequency ( self , frequency : int ) -> bool : return self . freq [ frequency ] > 0 # Your FrequencyTracker object will be instantiated and called as such: # obj = FrequencyTracker() # obj.add(number) # obj.deleteOne(number) # param_3 = obj.hasFrequency(frequency)
```