problemmediumalgorithmsleetcode-2671leetcode 2671leetcode2671

Frequency Tracker

MediumUpdated: Aug 2, 2025
Practice on:
LeetCode

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

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

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

Code

C++
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;
    }
};
Go
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
}
Java
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;
    }
}
Kotlin
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
    }
}
Python
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
Rust
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
    }
}
TypeScript
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.

Comments