Mutating counts without cleanup
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
Move from brute-force thinking to an efficient approach using hash map strategy.
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 <= 1052 * 105 calls will be made to add, deleteOne, and hasFrequency in total.Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Hash Map · Design
["FrequencyTracker","add","add","hasFrequency"] [[],[3],[3],[2]]
["FrequencyTracker","add","deleteOne","hasFrequency"] [[],[1],[1],[1]]
["FrequencyTracker","hasFrequency","add","hasFrequency"] [[],[2],[3],[1]]
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #2671: Frequency Tracker
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);
*/
// Accepted solution for LeetCode #2671: Frequency Tracker
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);
*/
# Accepted solution for LeetCode #2671: Frequency Tracker
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)
// Accepted solution for LeetCode #2671: Frequency Tracker
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)
}
}
// Accepted solution for LeetCode #2671: Frequency Tracker
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)
*/
Use this to step through a reusable interview workflow for this problem.
Use a simple list or array for storage. Each operation (get, put, remove) requires a linear scan to find the target element — O(n) per operation. Space is O(n) to store the data. The linear search makes this impractical for frequent operations.
Design problems target O(1) amortized per operation by combining data structures (hash map + doubly-linked list for LRU, stack + min-tracking for MinStack). Space is always at least O(n) to store the data. The challenge is achieving constant-time operations through clever structure composition.
Review these before coding to avoid predictable interview regressions.
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.