Problem statement

Keep a collection of numbers (duplicates allowed) and answer questions about how often numbers occur. Write the class FrequencyTracker:

• FrequencyTracker() starts with an empty collection.
• void add(int number) adds one copy of number.
• void deleteOne(int number) removes one copy of number if there is one; otherwise nothing happens.
• boolean hasFrequency(int frequency) returns whether some number occurs exactly frequency times in the collection.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every method that returns nothing.

Example 1

Input: ["FrequencyTracker","add","add","hasFrequency","add","hasFrequency","deleteOne","hasFrequency"]
[[],[5],[5],[2],[8],[1],[5],[2]]
Output: [null,null,null,true,null,true,null,false]
Explanation: 5 occurs twice, so frequency 2 exists. Adding 8 gives a number that occurs once. After one 5 is removed, 5 and 8 both occur once and nothing occurs twice.

Example 2

Input: ["FrequencyTracker","deleteOne","hasFrequency","add","deleteOne","deleteOne","hasFrequency"]
[[],[3],[1],[3],[3],[3],[1]]
Output: [null,null,false,null,null,null,false]
Explanation: Deleting a number that is not there does nothing. After 3 is added and removed, no number occurs once; the second removal of 3 is ignored.

Constraints

• 1 <= number <= 10^5
• 1 <= frequency <= 10^5
• At most 2 * 10^5 calls are made in total to add, deleteOne and hasFrequency

Hints for Frequency Tracker

1. Hint 1

   Counting how often each number occurs is a hash map. But hasFrequency asks the reverse question.

2. Hint 2

   Keep a second count: for every frequency f, how many distinct numbers currently occur exactly f times.

3. Hint 3

   When a number's count changes from c to c + 1 (or c - 1), one number leaves frequency c and joins the new one — update both tallies.

How to solve Frequency Tracker

Two maps: count[number] and numbersWith[f] — the number of distinct values whose count is exactly f. Every update moves one value from one frequency to a neighbouring one, and hasFrequency(f) is numbersWith[f] > 0.

Approach

1. add(x): let c = count[x]; if c > 0 decrease numbersWith[c]; set count[x] = c + 1 and increase numbersWith[c + 1].
2. deleteOne(x): let c = count[x]; if c == 0 do nothing. Otherwise decrease numbersWith[c], set count[x] = c - 1, and if c - 1 > 0 increase numbersWith[c - 1].
3. hasFrequency(f): return numbersWith[f] > 0.

Why it works

The invariant is that numbersWith[f] equals the number of values whose count is f (for f >= 1). An add or a delete changes exactly one value's count by one, so exactly one value leaves its old frequency and enters the new one, and the two adjustments keep the invariant.

Complexity

• Time — O(1) per call
• Space — O(n) for n distinct numbers

Pitfalls

• Deleting a number that is absent must not make its count negative or touch numbersWith.
• Do not record frequency 0 in numbersWith — hasFrequency is only asked for f >= 1, but a stray count there is a sign the bookkeeping is off.

Reference solution

Python

from collections import defaultdict

class FrequencyTracker:

    def __init__(self):
        self.count = defaultdict(int)        # number -> how often it occurs
        self.numbersWith = defaultdict(int)  # f -> how many numbers occur exactly f times

    def add(self, number: int) -> None:
        c = self.count[number]
        if c > 0:
            self.numbersWith[c] -= 1
        self.count[number] = c + 1
        self.numbersWith[c + 1] += 1

    def deleteOne(self, number: int) -> None:
        c = self.count[number]
        if c == 0:
            return
        self.numbersWith[c] -= 1
        self.count[number] = c - 1
        if c > 1:
            self.numbersWith[c - 1] += 1

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

Java

class FrequencyTracker {
    private HashMap<Integer, Integer> count = new HashMap<>();       // number -> occurrences
    private HashMap<Integer, Integer> numbersWith = new HashMap<>(); // f -> numbers occurring f times

    public FrequencyTracker() {
    }

    public void add(int number) {
        int c = count.getOrDefault(number, 0);
        if (c > 0) numbersWith.merge(c, -1, Integer::sum);
        count.put(number, c + 1);
        numbersWith.merge(c + 1, 1, Integer::sum);
    }

    public void deleteOne(int number) {
        int c = count.getOrDefault(number, 0);
        if (c == 0) return;
        numbersWith.merge(c, -1, Integer::sum);
        count.put(number, c - 1);
        if (c > 1) numbersWith.merge(c - 1, 1, Integer::sum);
    }

    public boolean hasFrequency(int frequency) {
        return numbersWith.getOrDefault(frequency, 0) > 0;
    }
}

C++

class FrequencyTracker {
    unordered_map<int, int> count;       // number -> how often it occurs
    unordered_map<int, int> numbersWith; // f -> how many numbers occur exactly f times
public:
    FrequencyTracker() {}

    void add(int number) {
        int c = count[number];
        if (c > 0) numbersWith[c]--;
        count[number] = c + 1;
        numbersWith[c + 1]++;
    }

    void deleteOne(int number) {
        auto it = count.find(number);
        if (it == count.end() || it->second == 0) return;
        int c = it->second;
        numbersWith[c]--;
        it->second = c - 1;
        if (c > 1) numbersWith[c - 1]++;
    }

    bool hasFrequency(int frequency) {
        auto it = numbersWith.find(frequency);
        return it != numbersWith.end() && it->second > 0;
    }
};

JavaScript

var FrequencyTracker = function() {
    this.count = new Map();       // number -> how often it occurs
    this.numbersWith = new Map(); // f -> how many numbers occur exactly f times
};

FrequencyTracker.prototype.bump = function(f, d) {
    this.numbersWith.set(f, (this.numbersWith.get(f) || 0) + d);
};

FrequencyTracker.prototype.add = function(number) {
    var c = this.count.get(number) || 0;
    if (c > 0) this.bump(c, -1);
    this.count.set(number, c + 1);
    this.bump(c + 1, 1);
};

FrequencyTracker.prototype.deleteOne = function(number) {
    var c = this.count.get(number) || 0;
    if (c === 0) return;
    this.bump(c, -1);
    this.count.set(number, c - 1);
    if (c > 1) this.bump(c - 1, 1);
};

FrequencyTracker.prototype.hasFrequency = function(frequency) {
    return (this.numbersWith.get(frequency) || 0) > 0;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More hash table problems

• Implement Router Medium
• Design Task Manager Medium
• Find Consecutive Integers from a Data Stream Medium
• Design Memory Allocator Medium
• Longest Uploaded Prefix Medium
• Design a Food Rating System Medium