2671. Frequency Tracker - Solution & Explanation

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

Approach overview

Problem Overview: You need to design a data structure that tracks numbers and their frequencies. Three operations must be supported: add(number), deleteOne(number), and hasFrequency(frequency). The tricky part is answering whether any number currently appears exactly frequency times without scanning the entire dataset.

Approach 1: Using Two Hash Maps (O(1) time per operation, O(n) space)

This approach maintains two hash maps. The first map count[number] stores how many times each number appears. The second map freq[f] stores how many numbers currently have frequency f. When you call add, increment the number's count and update both maps. When deleteOne is called, decrease the count and update the frequency tracking map accordingly. The key insight is that hasFrequency(f) becomes a constant-time lookup: simply check whether freq[f] > 0. This avoids iterating through all numbers and is the standard solution for problems involving dynamic frequency tracking using a hash table.

Approach 2: Using a List and Counter (O(1) average time, O(n) space)

If the value range is bounded, you can replace the primary hash map with an indexed list (array) where the index represents the number and the value stores its frequency. A separate counter structure tracks how many numbers currently have each frequency. Updates happen in constant time by decrementing the old frequency bucket and incrementing the new one. The array avoids hash lookups and can be slightly faster in languages like C++ or Java. The overall logic remains identical: maintain a mapping from numbers to counts and another structure that tracks how many numbers share the same count.

Both approaches rely on the same core idea: maintain frequency of frequencies. Without this second structure, answering hasFrequency would require scanning all counts, which costs O(n). Using a secondary tracker keeps every operation constant time and fits well with design-style problems that require efficient updates and queries.

Recommended for interviews: The two-hash-map solution is what interviewers expect. It clearly demonstrates understanding of frequency counting with a hash table and how to optimize repeated queries. A naive scan would work functionally but fails the performance requirement. Showing the frequency-of-frequencies optimization signals strong problem-solving and system design thinking.

Approach 1: Using Two Hash Maps

Using two hash maps: One will map numbers to their frequencies, and another will map frequencies to the count of numbers having that frequency. This allows for efficient updates and queries regarding frequencies.

Python

class FrequencyTracker:
    def __init__(self):
        self.num_count = {}
        self.freq_count = {}

    def add(self, number: int) -> None:
        curr_freq = self.num_count.get(number, 0)
        self.num_count[number] = curr_freq + 1
        if curr_freq > 0:
            self.freq_count[curr_freq] -= 1
            if self.freq_count[curr_freq] == 0:
                del self.freq_count[curr_freq]
        self.freq_count[self.num_count[number]] = self.freq_count.get(self.num_count[number], 0) + 1

    def deleteOne(self, number: int) -> None:
        if number in self.num_count and self.num_count[number] > 0:
            curr_freq = self.num_count[number]
            self.freq_count[curr_freq] -= 1
            if self.freq_count[curr_freq] == 0:
                del self.freq_count[curr_freq]
            self.num_count[number] -= 1
            if self.num_count[number] > 0:
                self.freq_count[self.num_count[number]] = self.freq_count.get(self.num_count[number], 0) + 1
            else:
                del self.num_count[number]

    def hasFrequency(self, frequency: int) -> bool:
        return frequency in self.freq_count and self.freq_count[frequency] > 0

JavaScript

class FrequencyTracker {
  constructor() {
    this.numCount = new Map();
    this.freqCount = new Map();
  }

  add(number) {
    const currentFreq = this.numCount.get(number) || 0;
    this.numCount.set(number, currentFreq + 1);

    if (currentFreq > 0) {
      this.freqCount.set(currentFreq, (this.freqCount.get(currentFreq) || 0) - 1);
      if (this.freqCount.get(currentFreq) === 0) {
        this.freqCount.delete(currentFreq);
      }
    }

    this.freqCount.set(currentFreq + 1, (this.freqCount.get(currentFreq + 1) || 0) + 1);
  }

  deleteOne(number) {
    if (!this.numCount.has(number) || this.numCount.get(number) === 0) return;

    const currentFreq = this.numCount.get(number);
    this.freqCount.set(currentFreq, this.freqCount.get(currentFreq) - 1);
    if (this.freqCount.get(currentFreq) === 0) {
      this.freqCount.delete(currentFreq);
    }

    this.numCount.set(number, currentFreq - 1);

    if (currentFreq > 1) {
      this.freqCount.set(currentFreq - 1, (this.freqCount.get(currentFreq - 1) || 0) + 1);
    } else {
      this.numCount.delete(number);
    }
  }

  hasFrequency(frequency) {
    return this.freqCount.has(frequency) && this.freqCount.get(frequency) > 0;
  }
}

This implementation uses a dictionary num_count to keep track of the number of times each number occurs, and another dictionary freq_count to track the number of numbers that have a particular frequency. When we add or delete a number, we update both dictionaries to maintain consistency.

Complexity

Time Complexity: O(1) for add, deleteOne, and hasFrequency operations.
Space Complexity: O(n), where n is the number of distinct numbers in the data structure.

Try this approach in the editor

Approach 2: Using a List and Counter

Alternatively, we can use a list to keep track of the elements and a counter to record the frequency of each element. This approach is less efficient but conceptually simpler for certain operations.

Java

import java.util.HashMap;

class FrequencyTracker {
    HashMap<Integer, Integer> numCount;
    HashMap<Integer, Integer> freqCount;

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

    public void add(int number) {
        int currFreq = numCount.getOrDefault(number, 0);
        numCount.put(number, currFreq + 1);
        if (currFreq > 0) {
            freqCount.put(currFreq, freqCount.get(currFreq) - 1);
            if (freqCount.get(currFreq) == 0) {
                freqCount.remove(currFreq);
            }
        }
        freqCount.put(currFreq + 1, freqCount.getOrDefault(currFreq + 1, 0) + 1);
    }

    public void deleteOne(int number) {
        if (!numCount.containsKey(number) || numCount.get(number) == 0)
            return;
        int currFreq = numCount.get(number);
        freqCount.put(currFreq, freqCount.get(currFreq) - 1);
        if (freqCount.get(currFreq) == 0) {
            freqCount.remove(currFreq);
        }
        numCount.put(number, currFreq - 1);
        if (currFreq > 1) {
            freqCount.put(currFreq - 1, freqCount.getOrDefault(currFreq - 1, 0) + 1);
        } else {
            numCount.remove(number);
        }
    }

    public boolean hasFrequency(int frequency) {
        return freqCount.containsKey(frequency) && freqCount.get(frequency) > 0;
    }
}

C++

#include <unordered_map>
#include <unordered_set>

class FrequencyTracker {
    std::unordered_map<int, int> num_count;
    std::unordered_map<int, int> freq_count;

public:
    void add(int number) {
        int curr_freq = num_count[number];
        if (curr_freq > 0) {
            freq_count[curr_freq]--;
            if (freq_count[curr_freq] == 0) {
                freq_count.erase(curr_freq);
            }
        }
        num_count[number] = curr_freq + 1;
        freq_count[num_count[number]]++;
    }

    void deleteOne(int number) {
        if (num_count.find(number) != num_count.end()) {
            int curr_freq = num_count[number];
            freq_count[curr_freq]--;
            if (freq_count[curr_freq] == 0) {
                freq_count.erase(curr_freq);
            }
            num_count[number]--;
            if (num_count[number] > 0) {
                freq_count[num_count[number]]++;
            } else {
                num_count.erase(number);
            }
        }
    }

    bool hasFrequency(int frequency) {
        return freq_count.find(frequency) != freq_count.end();
    }
};

This Java solution employs HashMap to store occurrences similar to our other efficient solutions. Handling and maintaining two hash maps allow quick insertion, deletion, and checking frequency presence.

Complexity

Time Complexity: O(1) for add, deleteOne, and hasFrequency operations.
Space Complexity: O(n), where n is the number of distinct numbers in the data structure.

Try this approach in the editor

Approach 3: 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.

TypeScript

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

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);
 */

Rust

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)
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Using Two Hash Maps	Time Complexity: O(1) for add, deleteOne, and hasFrequency operations. Space Complexity: O(n), where n is the number of distinct numbers in the data structure.
Using a List and Counter	Time Complexity: O(1) for add, deleteOne, and hasFrequency operations. Space Complexity: O(n), where n is the number of distinct numbers in the data structure.
Hash Table	–

Complexity analysis

Approach	Time	Space	When to Use
Two Hash Maps (Number Count + Frequency Count)	O(1) per operation	O(n)	General case; best interview solution with constant-time updates and queries
List + Frequency Counter	O(1) average per operation	O(n)	When number range is bounded and array indexing is faster than hash lookups

Frequently asked questions

Is Frequency Tracker easy or hard?

Frequency Tracker is considered a medium difficulty problem on LeetCode. The operations themselves are simple, but the challenge is recognizing that a second map tracking frequency counts is required to answer queries in constant time.

Frequency Tracker Python/Java solution

In Python or JavaScript, the typical implementation uses two dictionaries (hash maps). In Java or C++, developers often use HashMap or unordered_map along with an auxiliary frequency counter or array. The algorithmic idea remains the same regardless of language.

How to solve Frequency Tracker in O(n)?

The overall structure stores up to n distinct numbers, so space grows to O(n). Each operation itself runs in O(1) time by updating two structures: the count of each number and the number of elements that have a given frequency. Checking hasFrequency(f) simply verifies whether the frequency counter for f is greater than zero.

What is the best approach for Frequency Tracker?

The best approach uses two hash maps: one mapping numbers to their counts and another mapping frequencies to how many numbers have that frequency. This allows add, delete, and frequency queries to run in O(1) time. The key trick is maintaining a "frequency of frequencies" structure so hasFrequency() becomes a constant-time lookup.

Is Frequency Tracker asked at Google/Amazon/Meta?

Frequency-tracking design problems frequently appear in interviews at large tech companies because they test hash map reasoning and data structure design. Variants of this problem or similar frequency counting tasks have appeared in interviews at companies like Amazon and Meta, especially in mid-level backend or systems interviews.

What data structure is used in Frequency Tracker?

The core data structures are hash tables. One hash table tracks how many times each number appears, while another tracks how many numbers currently have a specific frequency. Some implementations replace the first hash map with an array when the value range is bounded.

What is the time complexity of Frequency Tracker?

With the optimal design, each operation—add, deleteOne, and hasFrequency—runs in O(1) time on average. The data structure uses hash map updates and lookups, which are constant time in typical implementations. Space complexity is O(n) where n is the number of distinct values stored.

Frequency Tracker solution and explanation

The problem

Approach overview

Approach 1: Using Two Hash Maps

Approach 2: Using a List and Counter

Approach 3: Hash Table

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Frequency Tracker solution and explanation

The problem

Approach overview

Approach 1: Using Two Hash Maps

Approach 2: Using a List and Counter

Approach 3: Hash Table

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems