2671. Frequency Tracker

Problem¶

Design a tracker supporting:

add(number): insert one occurrence.
deleteOne(number): remove one occurrence, if present.
hasFrequency(frequency): check whether any stored number occurs exactly that many times.

Operation          Stored values    Return
add(3)             [3]               None
add(3)             [3, 3]            None
hasFrequency(2)    [3, 3]            True
deleteOne(3)       [3]               None
hasFrequency(2)    [3]               False

class FrequencyTracker:
    def __init__(self):
        pass

    def add(self, number: int) -> None:
        pass

    def deleteOne(self, number: int) -> None:
        pass

    def hasFrequency(self, frequency: int) -> bool:
        pass

Key trick¶

Maintain two maps: number → occurrence count, and frequency → count of distinct numbers with that frequency.

Trap¶

Update both the old and new frequency buckets after every change.
Ignore deletion of absent numbers; never track frequency zero.
Dictionary membership answers queries correctly only if empty frequency buckets are removed.

Why is it interesting?¶

An extra index turns a scan over all numbers into a constant-time query, at the cost of maintaining a small invariant during updates.

Python solution¶

class FrequencyTracker:
    def __init__(self):
        self.counts = {}
        self.freqs = {}

    def _change(self, number: int, delta: int) -> None:
        prev = self.counts.get(number, 0)
        cur = prev + delta

        # Remove this number from its previous positive-frequency bucket.
        if prev:
            self.freqs[prev] -= 1
            if self.freqs[prev] == 0:
                del self.freqs[prev]

        # Only numbers currently present belong in either map.
        if cur:
            self.counts[number] = cur
            self.freqs[cur] = self.freqs.get(cur, 0) + 1
        else:
            del self.counts[number]

    def add(self, number: int) -> None:
        self._change(number, 1)

    def deleteOne(self, number: int) -> None:
        if number in self.counts:
            self._change(number, -1)

    def hasFrequency(self, frequency: int) -> bool:
        return frequency in self.freqs

Time: Expected \(O(1)\) per operation.

Space: \(O(d)\), where \(d\) is the number of distinct values currently stored.

Comment on my solution¶

Both versions are correct and achieve expected \(O(1)\) per operation.
The first removes zero-count entries, so membership checks are valid and space depends on currently stored distinct numbers.
The second simplifies updates by retaining zero-count entries; its positive-count checks are essential, and memory can grow with historical numbers and frequencies.
A shared update helper removes the duplicated bucket-maintenance logic.
If both definitions appear in one module, the second replaces the first.

# WORKS
class FrequencyTracker:

    def __init__(self):
        self.num_freq = {}
        self.freq_cnt = {}

    def add(self, number: int) -> None:
        self.num_freq[number] = self.num_freq.get(number, 0) + 1
        freq = self.num_freq[number]
        freq_prev = freq - 1
        if freq_prev:
            self.freq_cnt[freq_prev] -= 1
            if self.freq_cnt[freq_prev] == 0:
                del self.freq_cnt[freq_prev]
        self.freq_cnt[freq] = self.freq_cnt.get(freq, 0) + 1

    def deleteOne(self, number: int) -> None:
        if number in self.num_freq:
            self.num_freq[number] -= 1
            freq = self.num_freq[number]
            freq_prev = freq + 1

            self.freq_cnt[freq_prev] -= 1
            if self.freq_cnt[freq_prev] == 0:
                del self.freq_cnt[freq_prev]

            if freq:
                self.freq_cnt[freq] = self.freq_cnt.get(freq, 0) + 1
            else:
                del self.num_freq[number]

    def hasFrequency(self, frequency: int) -> bool:
        return frequency in self.freq_cnt


# WORKS
class FrequencyTracker:

    def __init__(self):
        self.num_freq = {}
        self.freq_cnt = {}

    def add(self, number: int) -> None:
        self.num_freq[number] = self.num_freq.get(number, 0) + 1
        freq = self.num_freq[number]
        freq_prev = freq - 1
        if freq_prev:
            self.freq_cnt[freq_prev] -= 1
        self.freq_cnt[freq] = self.freq_cnt.get(freq, 0) + 1

    def deleteOne(self, number: int) -> None:
        if self.num_freq.get(number, 0):
            self.num_freq[number] -= 1
            freq = self.num_freq[number]
            freq_prev = freq + 1
            self.freq_cnt[freq_prev] -= 1
            if freq:
                self.freq_cnt[freq] = self.freq_cnt.get(freq, 0) + 1

    def hasFrequency(self, frequency: int) -> bool:
        return self.freq_cnt.get(frequency, 0) > 0