2671. Frequency Tracker
Problem Description
The problem requires us to design a data structure called FrequencyTracker
that can track the number of occurrences, or frequencies, of numbers added to it. The FrequencyTracker
should be able to perform the following operations:
- Initialization with an empty data structure.
- Adding a number to the data structure using the
add
method. - Deleting a single occurrence of a number from the data structure with the
deleteOne
method. If the number is not present, no action is taken. - Checking if there is any number in the data structure that appears exactly a given number of times with the
hasFrequency
method.
A key challenge of this problem is efficiently updating and querying the frequency of numbers in the data structure since the operations can occur numerous times.
Intuition
The intuition behind the solution is to use two hash-based data structures, where we map numbers to their frequencies and frequencies to the count of numbers having them.
When adding a number, we increment its frequency count in the cnt
dictionary and update the frequency counts in the freq
dictionary accordingly. If a frequency count goes to zero, it's important to decrement the count of numbers that previously had that frequency.
Similarly, when deleting a number, we decrease the number's frequency in cnt
and update the frequency counts in the freq
.
The hasFrequency
method is straightforward: it directly checks if there is any number with the given frequency by looking it up in the freq
dictionary.
The primary goal is to keep these operations at constant time complexity, O(1)
, which is attainable through effective use of the hash maps provided by the defaultdict
from Python's collections module. By keeping direct mappings of frequencies and their counts, we avoid the need to iterate through our data structure to find frequencies, which would increase the time complexity significantly.
Solution Approach
In the given solution, we utilize two dictionaries from the Python collections
library. The defaultdict
type is used to automatically create dictionary entries with a default value of 0
for new keys.
Let's examine each method of the FrequencyTracker
class to understand its inner workings:
-
The
__init__
method sets up our data structure with twodefaultdict
instances namedcnt
andfreq
.cnt
keeps track of the frequency for each number whilefreq
tracks how many numbers have a particular frequency. -
The
add
method increases the frequency of the givennumber
. It performs the following steps:-
Checks if the current frequency of the number is greater than 0. This means we have some numbers with this frequency, and since we're about to increase this
number
's frequency, we need to decrease the count of numbers with the current frequency. Hence, we doself.freq[self.cnt[number]] -= 1
. -
Increases the frequency of the number by one in the
cnt
dictionary withself.cnt[number] += 1
. -
Accounts for the new frequency by incrementing its count in the
freq
dictionary withself.freq[self.cnt[number]] += 1
.
-
-
The
deleteOne
method removes one occurrence of the givennumber
. Its steps are:-
It checks whether the
number
is present incnt
. If its count is at0
, we do nothing as there's nothing to delete. -
If the
number
exists, it decreases the count of numbers with the current frequency by updatingself.freq[self.cnt[number]]
. -
It then decrements the count of the
number
incnt
withself.cnt[number] -= 1
. -
Finally, it increments the count of numbers with the new (decreased) frequency since the
number
now belongs to this new frequency category.
-
-
The
hasFrequency
method simply returns whether the givenfrequency
has a non-zero count in thefreq
dictionary with the expressionself.freq[frequency] > 0
. If the count is greater than 0, then there's at least one number in our data structure that has the queried frequency, so it returnsTrue
. Otherwise, it returnsFalse
.
This solution leverages the power of hash maps for efficient lookups and updates. The operationsāadd
, deleteOne
, and hasFrequency
āall work in constant time, O(1)
, since they involve a fixed number of hash map updates and lookups, making this solution highly optimal for the problem at hand.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach by walking through a small example that demonstrates how the FrequencyTracker
would operate:
-
We start by initializing our
FrequencyTracker
, which sets up our twodefaultdict
instances:cnt
andfreq
. -
Next, we call the
add
method with the number5
. Since5
is not incnt
, it gets a default value of0
. We then increment this to1
incnt[5]
. Our dictionaries now look like this:cnt
:{5: 1}
freq
:{1: 1}
(meaning there is 1 number with a frequency of 1)
-
We add the number
5
again. Thefreq[cnt[5]]
which was1
is decremented to0
, as weāre about to increment the frequency of5
. After incrementingcnt[5]
, we also incrementfreq[2]
to1
. The dictionaries are now:cnt
:{5: 2}
freq
:{1: 0, 2: 1}
-
Suppose we add a different number, say
3
. Just like when we first added5
,cnt
andfreq
are updated respectively:cnt
:{5: 2, 3: 1}
freq
:{1: 1, 2: 1}
-
Now we want to delete one occurrence of the number
5
usingdeleteOne
. This results in decreasingcnt[5]
and also updatingfreq
accordingly:cnt
:{5: 1, 3: 1}
freq
:{1: 2, 2: 0}
(since we now have two numbers with a frequency of 1)
-
Let's try to delete a number that hasn't been added, for instance
deleteOne(7)
. Since7
is not incnt
, nothing changes, andcnt
andfreq
remain the same. -
Finally, using
hasFrequency
, we check if there is a number with a frequency of1
. Sincefreq[1]
is2
, we returnTrue
because there are two numbers (3 and 5 after the deletion happened) with a frequency of 1.
This small example walks us through a series of operations that fulfill the objectives of the FrequencyTracker
. Each step involves a certain number of constant-time hash map operations, thus maintaining the O(1)
time complexity for all operations in the data structure.
Solution Implementation
1from collections import defaultdict
2
3class FrequencyTracker:
4 def __init__(self):
5 # Initialize a dictionary to store the count of each number
6 self.number_count = defaultdict(int)
7 # Initialize a dictionary to store the count of frequencies
8 self.frequency_count = defaultdict(int)
9
10 def add(self, number: int) -> None:
11 # If the number is already present, decrease its old frequency count
12 if self.frequency_count[self.number_count[number]] > 0:
13 self.frequency_count[self.number_count[number]] -= 1
14
15 # Increment the count of the number
16 self.number_count[number] += 1
17 # Increment the count of the new frequency
18 self.frequency_count[self.number_count[number]] += 1
19
20 def deleteOne(self, number: int) -> None:
21 # If the number is not present, there is nothing to delete
22 if self.number_count[number] == 0:
23 return
24
25 # Decrease the frequency count of the number's current count
26 self.frequency_count[self.number_count[number]] -= 1
27 # Decrement the count of the number
28 self.number_count[number] -= 1
29 # If the new count is not zero, increment the frequency count of the new count
30 self.frequency_count[self.number_count[number]] += 1
31
32 def hasFrequency(self, frequency: int) -> bool:
33 # Check if the frequency count is greater than 0,
34 # which means there is at least one number with the given frequency
35 return self.frequency_count[frequency] > 0
36
1import java.util.HashMap;
2import java.util.Map;
3
4public class FrequencyTracker {
5
6 // This map maintains the count of occurrences for each number.
7 private Map<Integer, Integer> numberFrequencyMap = new HashMap<>();
8
9 // This map maintains the frequency of frequencies.
10 private Map<Integer, Integer> frequencyCountMap = new HashMap<>();
11
12 // Constructor for FrequencyTracker class
13 public FrequencyTracker() {
14 // No initialization is needed since we're using HashMaps.
15 }
16
17 // Method to add a number and update frequency tracking.
18 public void add(int number) {
19 // First, get the current frequency of the number, defaulting to zero if not present.
20 int currentFrequency = numberFrequencyMap.getOrDefault(number, 0);
21
22 // Decrease the count of the frequency that the number currently has, if it is greater than 0.
23 if (frequencyCountMap.getOrDefault(currentFrequency, 0) > 0) {
24 frequencyCountMap.merge(currentFrequency, -1, Integer::sum);
25 }
26
27 // Increase the frequency of the number by 1.
28 numberFrequencyMap.merge(number, 1, Integer::sum);
29
30 // Increase the count of the new frequency the number now has.
31 frequencyCountMap.merge(currentFrequency + 1, 1, Integer::sum);
32 }
33
34 // Method to delete a single occurrence of a number and update frequency tracking.
35 public void deleteOne(int number) {
36 // Retrieve the current frequency of the number, defaulting to zero if not present.
37 int currentFrequency = numberFrequencyMap.getOrDefault(number, 0);
38
39 // If the number is not tracked or its count is zero, do nothing.
40 if (currentFrequency == 0) {
41 return;
42 }
43
44 // Decrease the count of the frequency that the number currently has.
45 frequencyCountMap.merge(currentFrequency, -1, Integer::sum);
46
47 // Decrease the frequency of the number by 1.
48 numberFrequencyMap.merge(number, -1, Integer::sum);
49
50 // If the frequency becomes zero, remove it from the map.
51 if (numberFrequencyMap.get(number) == 0) {
52 numberFrequencyMap.remove(number);
53 } else {
54 // Increase the count of the new frequency the number now has.
55 frequencyCountMap.merge(currentFrequency - 1, 1, Integer::sum);
56 }
57 }
58
59 // Method to check if there is any number that has exactly the given frequency.
60 public boolean hasFrequency(int frequency) {
61 // Return true if the frequency is present and there are numbers with that frequency; otherwise, false.
62 return frequencyCountMap.getOrDefault(frequency, 0) > 0;
63 }
64}
65
66// Sample usage:
67// FrequencyTracker tracker = new FrequencyTracker();
68// tracker.add(number); // Adds a number to the tracker.
69// tracker.deleteOne(number); // Removes one occurrence of the number.
70// boolean hasFreq = tracker.hasFrequency(frequency); // Checks if any number has the given frequency.
71
1#include <unordered_map>
2using namespace std;
3
4class FrequencyTracker {
5public:
6 FrequencyTracker() {
7 // Constructor, no initialization needed since the maps are empty
8 }
9
10 // Adds a number to the tracker
11 void add(int number) {
12 // Fetch the current frequency of the number
13 int currentFrequency = numberCount[number];
14 // If the number is already present, decrement its count in the frequency map
15 if (currentFrequency > 0) {
16 frequencyCount[currentFrequency]--;
17 }
18 // Increment the count of the number
19 numberCount[number]++;
20 // Increment the count of the new frequency
21 frequencyCount[currentFrequency + 1]++;
22 }
23
24 // Deletes a single instance of a number from the tracker
25 void deleteOne(int number) {
26 // Fetch the current frequency of the number
27 int currentFrequency = numberCount[number];
28 // Return early if the number does not exist in the tracker
29 if (currentFrequency == 0) {
30 return;
31 }
32 // Decrement the frequency count of the number's current frequency
33 frequencyCount[currentFrequency]--;
34 // Decrement the number's count
35 numberCount[number]--;
36 // Increment the count of the new frequency
37 frequencyCount[currentFrequency - 1]++;
38 }
39
40 // Checks if any number has the specified frequency
41 bool hasFrequency(int frequency) {
42 // Return true if the frequency count is greater than 0
43 return frequencyCount[frequency] > 0;
44 }
45
46private:
47 // A map to store the counts of individual numbers
48 unordered_map<int, int> numberCount;
49 // A map to store the frequencies of counts
50 unordered_map<int, int> frequencyCount;
51};
52
53/**
54 * Your FrequencyTracker object will be instantiated and called as such:
55 * FrequencyTracker* obj = new FrequencyTracker();
56 * obj->add(number);
57 * obj->deleteOne(number);
58 * bool freqExists = obj->hasFrequency(frequency);
59 */
60
1// This map keeps track of the count of each number.
2const countMap: Map<number, number> = new Map();
3
4// This map keeps track of the frequency of each count.
5const frequencyMap: Map<number, number> = new Map();
6
7/**
8 * Adds a number to the tracker, increasing its count.
9 * @param {number} number - The number to add.
10 */
11function add(number: number): void {
12 // Retrieve the current count for the number, default to 0.
13 const currentCount = countMap.get(number) || 0;
14
15 // Decrease the frequency of the current count, if any.
16 if (currentCount > 0) {
17 frequencyMap.set(currentCount, (frequencyMap.get(currentCount) || 0) - 1);
18 }
19
20 // Increase the count of the number.
21 countMap.set(number, currentCount + 1);
22
23 // Increase the frequency of the new count.
24 frequencyMap.set(currentCount + 1, (frequencyMap.get(currentCount + 1) || 0) + 1);
25}
26
27/**
28 * Deletes one instance of a number from the tracker.
29 * @param {number} number - The number to delete.
30 */
31function deleteOne(number: number): void {
32 // Retrieve the current count for the number, default to 0.
33 const currentCount = countMap.get(number) || 0;
34
35 // If the count is zero, exit the function as there is nothing to delete.
36 if (currentCount === 0) {
37 return;
38 }
39
40 // Decrease the frequency of the current count.
41 frequencyMap.set(currentCount, (frequencyMap.get(currentCount) || 0) - 1);
42
43 // Update the count map to reflect one less of the number.
44 if (currentCount - 1 > 0) {
45 countMap.set(number, currentCount - 1);
46 frequencyMap.set(currentCount - 1, (frequencyMap.get(currentCount - 1) || 0) + 1);
47 } else {
48 // If the new count is 0, remove the number from the countMap.
49 countMap.delete(number);
50 }
51}
52
53/**
54 * Checks if any number has a specific frequency count.
55 * @param {number} frequency - The frequency to check.
56 * @returns {boolean} - True if any number has the specified frequency count.
57 */
58function hasFrequency(frequency: number): boolean {
59 return (frequencyMap.get(frequency) || 0) > 0;
60}
61
Time and Space Complexity
Time Complexity
-
__init__
: The initialization method's time complexity isO(1)
since it only involves initializing twodefaultdict
data structures. -
add
method: Theadd
method has a time complexity ofO(1)
. This is because it performs a constant amount of work - updating dictionaries - regardless of the size of the input data. -
deleteOne
method: Similar to theadd
method,deleteOne
also has a time complexity ofO(1)
for the same reasons. -
hasFrequency
method: ThehasFrequency
method again has a time complexity ofO(1)
as it only checks the value associated with a key in a dictionary.
Space Complexity
- The space complexity of the
FrequencyTracker
class isO(n)
wheren
is the number of unique numbers that have been added to the tracker. This is due to the fact that each unique number requires space in both thecnt
andfreq
dictionaries. The space taken by these dictionaries scales with the number of unique numbers added.
Learn more about how to find time and space complexity quickly using problem constraints.
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time