2671. Frequency Tracker

MediumDesignHash Table
Leetcode Link

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

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 two defaultdict instances named cnt and freq. cnt keeps track of the frequency for each number while freq tracks how many numbers have a particular frequency.

  • The add method increases the frequency of the given number. It performs the following steps:

    1. 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 do self.freq[self.cnt[number]] -= 1.

    2. Increases the frequency of the number by one in the cnt dictionary with self.cnt[number] += 1.

    3. Accounts for the new frequency by incrementing its count in the freq dictionary with self.freq[self.cnt[number]] += 1.

  • The deleteOne method removes one occurrence of the given number. Its steps are:

    1. It checks whether the number is present in cnt. If its count is at 0, we do nothing as there's nothing to delete.

    2. If the number exists, it decreases the count of numbers with the current frequency by updating self.freq[self.cnt[number]].

    3. It then decrements the count of the number in cnt with self.cnt[number] -= 1.

    4. 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 given frequency has a non-zero count in the freq dictionary with the expression self.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 returns True. Otherwise, it returns False.

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which technique can we use to find the middle of a linked list?

Example Walkthrough

Let's illustrate the solution approach by walking through a small example that demonstrates how the FrequencyTracker would operate:

  1. We start by initializing our FrequencyTracker, which sets up our two defaultdict instances: cnt and freq.

  2. Next, we call the add method with the number 5. Since 5 is not in cnt, it gets a default value of 0. We then increment this to 1 in cnt[5]. Our dictionaries now look like this:

    • cnt: {5: 1}
    • freq: {1: 1} (meaning there is 1 number with a frequency of 1)

  3. We add the number 5 again. The freq[cnt[5]] which was 1 is decremented to 0, as we’re about to increment the frequency of 5. After incrementing cnt[5], we also increment freq[2] to 1. The dictionaries are now:

    • cnt: {5: 2}
    • freq: {1: 0, 2: 1}

  4. Suppose we add a different number, say 3. Just like when we first added 5, cnt and freq are updated respectively:

    • cnt: {5: 2, 3: 1}
    • freq: {1: 1, 2: 1}

  5. Now we want to delete one occurrence of the number 5 using deleteOne. This results in decreasing cnt[5] and also updating freq accordingly:

    • cnt: {5: 1, 3: 1}
    • freq: {1: 2, 2: 0} (since we now have two numbers with a frequency of 1)

  6. Let's try to delete a number that hasn't been added, for instance deleteOne(7). Since 7 is not in cnt, nothing changes, and cnt and freq remain the same.

  7. Finally, using hasFrequency, we check if there is a number with a frequency of 1. Since freq[1] is 2, we return True 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
Not Sure What to Study? Take the 2-min Quiz：

Which data structure is used in a depth first search?

Time and Space Complexity

Time Complexity

  • __init__: The initialization method's time complexity is O(1) since it only involves initializing two defaultdict data structures.

  • add method: The add method has a time complexity of O(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 the add method, deleteOne also has a time complexity of O(1) for the same reasons.

  • hasFrequency method: The hasFrequency method again has a time complexity of O(1) as it only checks the value associated with a key in a dictionary.

Space Complexity

  • The space complexity of the FrequencyTracker class is O(n) where n 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 the cnt and freq 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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of these pictures shows the visit order of a depth-first search?

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

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 to Algo Cheat Sheet

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

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫