Frequency Tracker

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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


**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^5
1 <= frequency <= 10^5
At most, 2 * 10^5 calls will be made to add, deleteOne, and hasFrequency in total.

Solution

Method 1 – Hash Map Frequency and Reverse Frequency Tracking

Intuition

We need to efficiently support adding, deleting, and checking for any number with a given frequency. By maintaining two hash maps—one for the count of each number and one for the count of each frequency—we can update and query in constant time.

Approach

Use a hash map cnt to store the count of each number.
Use another hash map freq to store how many numbers have a given frequency.
On add(number), increment cnt[number] and update freq for the old and new frequencies.
On deleteOne(number), decrement cnt[number] (if present) and update freq for the old and new frequencies.
On hasFrequency(frequency), check if freq[frequency] > 0.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class FrequencyTracker {
    unordered_map<int, int> cnt, freq;
public:
    FrequencyTracker() {}
    void add(int number) {
        freq[cnt[number]]--;
        cnt[number]++;
        freq[cnt[number]]++;
    }
    void deleteOne(int number) {
        if (cnt[number] > 0) {
            freq[cnt[number]]--;
            cnt[number]--;
            freq[cnt[number]]++;
        }
    }
    bool hasFrequency(int frequency) {
        return freq[frequency] > 0;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


type FrequencyTracker struct {
    cnt  map[int]int
    freq map[int]int
}
func Constructor() FrequencyTracker {
    return FrequencyTracker{make(map[int]int), make(map[int]int)}
}
func (ft *FrequencyTracker) Add(number int) {
    ft.freq[ft.cnt[number]]--
    ft.cnt[number]++
    ft.freq[ft.cnt[number]]++
}
func (ft *FrequencyTracker) DeleteOne(number int) {
    if ft.cnt[number] > 0 {
        ft.freq[ft.cnt[number]]--
        ft.cnt[number]--
        ft.freq[ft.cnt[number]]++
    }
}
func (ft *FrequencyTracker) HasFrequency(frequency int) bool {
    return ft.freq[frequency] > 0
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class FrequencyTracker {
    private Map<Integer, Integer> cnt = new HashMap<>();
    private Map<Integer, Integer> freq = new HashMap<>();
    public FrequencyTracker() {}
    public void add(int number) {
        freq.put(cnt.getOrDefault(number, 0), freq.getOrDefault(cnt.getOrDefault(number, 0), 0) - 1);
        cnt.put(number, cnt.getOrDefault(number, 0) + 1);
        freq.put(cnt.get(number), freq.getOrDefault(cnt.get(number), 0) + 1);
    }
    public void deleteOne(int number) {
        if (cnt.getOrDefault(number, 0) > 0) {
            freq.put(cnt.get(number), freq.get(cnt.get(number)) - 1);
            cnt.put(number, cnt.get(number) - 1);
            freq.put(cnt.get(number), freq.getOrDefault(cnt.get(number), 0) + 1);
        }
    }
    public boolean hasFrequency(int frequency) {
        return freq.getOrDefault(frequency, 0) > 0;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class FrequencyTracker {
    private val cnt = mutableMapOf<Int, Int>()
    private val freq = mutableMapOf<Int, Int>()
    fun add(number: Int) {
        freq[cnt.getOrDefault(number, 0)] = freq.getOrDefault(cnt.getOrDefault(number, 0), 0) - 1
        cnt[number] = cnt.getOrDefault(number, 0) + 1
        freq[cnt[number]!!] = freq.getOrDefault(cnt[number]!!, 0) + 1
    }
    fun deleteOne(number: Int) {
        if (cnt.getOrDefault(number, 0) > 0) {
            freq[cnt[number]!!] = freq.getOrDefault(cnt[number]!!, 0) - 1
            cnt[number] = cnt.getOrDefault(number, 0) - 1
            freq[cnt[number]!!] = freq.getOrDefault(cnt[number]!!, 0) + 1
        }
    }
    fun hasFrequency(frequency: Int): Boolean {
        return freq.getOrDefault(frequency, 0) > 0
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class FrequencyTracker:
    def __init__(self):
        self.cnt: dict[int, int] = {}
        self.freq: dict[int, int] = {}
    def add(self, number: int) -> None:
        self.freq[self.cnt.get(number, 0)] = self.freq.get(self.cnt.get(number, 0), 0) - 1
        self.cnt[number] = self.cnt.get(number, 0) + 1
        self.freq[self.cnt[number]] = self.freq.get(self.cnt[number], 0) + 1
    def deleteOne(self, number: int) -> None:
        if self.cnt.get(number, 0) > 0:
            self.freq[self.cnt[number]] = self.freq.get(self.cnt[number], 0) - 1
            self.cnt[number] -= 1
            self.freq[self.cnt[number]] = self.freq.get(self.cnt[number], 0) + 1
    def hasFrequency(self, frequency: int) -> bool:
        return self.freq.get(frequency, 0) > 0

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


use std::collections::HashMap;
struct FrequencyTracker {
    cnt: HashMap<i32, i32>,
    freq: HashMap<i32, i32>,
}
impl FrequencyTracker {
    fn new() -> Self {
        Self { cnt: HashMap::new(), freq: HashMap::new() }
    }
    fn add(&mut self, number: i32) {
        *self.freq.entry(*self.cnt.get(&number).unwrap_or(&0)).or_insert(0) -= 1;
        *self.cnt.entry(number).or_insert(0) += 1;
        *self.freq.entry(*self.cnt.get(&number).unwrap()).or_insert(0) += 1;
    }
    fn delete_one(&mut self, number: i32) {
        if *self.cnt.get(&number).unwrap_or(&0) > 0 {
            *self.freq.entry(*self.cnt.get(&number).unwrap()).or_insert(0) -= 1;
            *self.cnt.entry(number).or_insert(0) -= 1;
            *self.freq.entry(*self.cnt.get(&number).unwrap()).or_insert(0) += 1;
        }
    }
    fn has_frequency(&self, frequency: i32) -> bool {
        *self.freq.get(&frequency).unwrap_or(&0) > 0
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class FrequencyTracker {
  private cnt: Map<number, number> = new Map();
  private freq: Map<number, number> = new Map();
  add(number: number): void {
    this.freq.set(this.cnt.get(number) ?? 0, (this.freq.get(this.cnt.get(number) ?? 0) ?? 0) - 1);
    this.cnt.set(number, (this.cnt.get(number) ?? 0) + 1);
    this.freq.set(this.cnt.get(number)!, (this.freq.get(this.cnt.get(number)!) ?? 0) + 1);
  }
  deleteOne(number: number): void {
    if ((this.cnt.get(number) ?? 0) > 0) {
      this.freq.set(this.cnt.get(number)!, (this.freq.get(this.cnt.get(number)!) ?? 0) - 1);
      this.cnt.set(number, (this.cnt.get(number) ?? 0) - 1);
      this.freq.set(this.cnt.get(number)!, (this.freq.get(this.cnt.get(number)!) ?? 0) + 1);
    }
  }
  hasFrequency(frequency: number): boolean {
    return (this.freq.get(frequency) ?? 0) > 0;
  }
}

Complexity

⏰ Time complexity: O(1) for all operations, since hash maps provide constant time access.
🧺 Space complexity: O(n), where n is the number of unique numbers tracked.

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Constraints#

Solution#

Method 1 – Hash Map Frequency and Reverse Frequency Tracking#

Intuition#

Approach#

Code#

Complexity#