Description
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 <= 1051 <= frequency <= 105- At most,
2 * 105 calls will be made to add, deleteOne, and hasFrequency in total.
Solutions
Solution 1: Hash Table
We define two hash tables, where cnt is used to record the occurrence count of each number, and freq is used to record the count of numbers with each frequency.
For the add operation, we directly decrement the value corresponding to cnt[number] in the hash table freq, then increment cnt[number], and finally increment the value corresponding to cnt[number] in freq.
For the deleteOne operation, we first check if cnt[number] is greater than zero. If it is, we decrement the value corresponding to cnt[number] in the hash table freq, then decrement cnt[number], and finally increment the value corresponding to cnt[number] in freq.
For the hasFrequency operation, we directly return whether freq[frequency] is greater than zero.
In terms of time complexity, since we use hash tables, the time complexity of each operation is O(1). The space complexity is O(n), where n is the number of distinct numbers.
PythonJavaC++GoTypeScriptRust
class FrequencyTracker:
def __init__(self):
self.cnt = defaultdict(int)
self.freq = defaultdict(int)
def add(self, number: int) -> None:
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]:
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)(code-box)
class FrequencyTracker {
private Map<Integer, Integer> cnt = new HashMap<>();
private Map<Integer, Integer> freq = new HashMap<>();
public FrequencyTracker() {
}
public void add(int number) {
freq.merge(cnt.getOrDefault(number, 0), -1, Integer::sum);
cnt.merge(number, 1, Integer::sum);
freq.merge(cnt.get(number), 1, Integer::sum);
}
public void deleteOne(int number) {
if (cnt.getOrDefault(number, 0) > 0) {
freq.merge(cnt.get(number), -1, Integer::sum);
cnt.merge(number, -1, Integer::sum);
freq.merge(cnt.get(number), 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);
*/(code-box)
class FrequencyTracker {
public:
FrequencyTracker() {
}
void add(int number) {
freq[cnt[number]]--;
cnt[number]++;
freq[cnt[number]]++;
}
void deleteOne(int number) {
if (cnt[number]) {
freq[cnt[number]]--;
cnt[number]--;
freq[cnt[number]]++;
}
}
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);
*/(code-box)
type FrequencyTracker struct {
cnt map[int]int
freq map[int]int
}
func Constructor() FrequencyTracker {
return FrequencyTracker{map[int]int{}, map[int]int{}}
}
func (this *FrequencyTracker) Add(number int) {
this.freq[this.cnt[number]]--
this.cnt[number]++
this.freq[this.cnt[number]]++
}
func (this *FrequencyTracker) DeleteOne(number int) {
if this.cnt[number] > 0 {
this.freq[this.cnt[number]]--
this.cnt[number]--
this.freq[this.cnt[number]]++
}
}
func (this *FrequencyTracker) HasFrequency(frequency int) bool {
return this.freq[frequency] > 0
}
/**
* Your FrequencyTracker object will be instantiated and called as such:
* obj := Constructor();
* obj.Add(number);
* obj.DeleteOne(number);
* param_3 := obj.HasFrequency(frequency);
*/(code-box)
class FrequencyTracker {
private cnt: Map<number, number>;
private freq: Map<number, number>;
constructor() {
this.cnt = new Map();
this.freq = new Map();
}
add(number: number): void {
const f = this.cnt.get(number) || 0;
this.freq.set(f, (this.freq.get(f) || 0) - 1);
this.cnt.set(number, f + 1);
this.freq.set(f + 1, (this.freq.get(f + 1) || 0) + 1);
}
deleteOne(number: number): void {
const f = this.cnt.get(number) || 0;
if (f > 0) {
this.freq.set(f, (this.freq.get(f) || 0) - 1);
this.cnt.set(number, f - 1);
this.freq.set(f - 1, (this.freq.get(f - 1) || 0) + 1);
}
}
hasFrequency(frequency: number): boolean {
return (this.freq.get(frequency) || 0) > 0;
}
}
/**
* Your FrequencyTracker object will be instantiated and called as such:
* var obj = new FrequencyTracker()
* obj.add(number)
* obj.deleteOne(number)
* var param_3 = obj.hasFrequency(frequency)
*/(code-box)
use std::collections::HashMap;
struct FrequencyTracker {
cnt: HashMap<i32, i32>,
freq: HashMap<i32, i32>,
}
/**
* `&self` means the method takes an immutable reference.
* If you need a mutable reference, change it to `&mut self` instead.
*/
impl FrequencyTracker {
fn new() -> Self {
FrequencyTracker {
cnt: HashMap::new(),
freq: HashMap::new(),
}
}
fn add(&mut self, number: i32) {
let count = self.cnt.entry(number).or_insert(0);
let prev_freq = self.freq.entry(*count).or_insert(0);
*prev_freq -= 1;
*count += 1;
let new_freq = self.freq.entry(*count).or_insert(0);
*new_freq += 1;
}
fn delete_one(&mut self, number: i32) {
if let Some(count) = self.cnt.get_mut(&number) {
if *count > 0 {
if let Some(prev_freq) = self.freq.get_mut(count) {
*prev_freq -= 1;
}
*count -= 1;
if let Some(new_freq) = self.freq.get_mut(count) {
*new_freq += 1;
}
}
}
}
fn has_frequency(&self, frequency: i32) -> bool {
self.freq.get(&frequency).map_or(false, |&freq| freq > 0)
}
}(code-box)
