All-one frequency buckets: increment, decrement, and read both extremes

Last updated: 4 Oct 20269 min read

tutorial

An all-one counter keeps a doubly linked list of nonempty frequency buckets in increasing count order. Each bucket owns a set of keys at one count, and a hash map points each live key to its bucket. Increment moves a key into the next bucket, creating that adjacent count bucket if absent. Decrement moves it backward or deletes it when its count falls from one to zero. Empty buckets are removed immediately. The first live bucket holds a minimum-count key; the last holds a maximum-count key. The API may return any key when several share an extreme frequency. This is a mutable in-memory count index, not a time-decayed stream estimate or an LFU cache with a tie-breaking eviction policy.

Operational case

Record dock-47 three times, dock-19 twice, and dock-61 once. The minimum key is dock-61 and the maximum is dock-47. After decrementing dock-47 twice, both dock-47 and dock-61 are at count one, so either is an acceptable minimum; dock-19 is the unique maximum. Removing dock-61's last count leaves dock-47 as the minimum and dock-19 as the maximum. Decrementing an absent code raises an error instead of creating a negative count. When the index is empty, both endpoint reads return no key.

Working Python program

class FrequencyBucket:
    def __init__(self, count):
        self.count = count
        self.keys = set()
        self.previous = None
        self.next = None


class AlertFrequencyIndex:
    def __init__(self):
        self.head = FrequencyBucket(0)
        self.tail = FrequencyBucket(0)
        self.head.next = self.tail
        self.tail.previous = self.head
        self.location = {}

    def _insert_after(self, anchor, count):
        bucket = FrequencyBucket(count)
        bucket.previous, bucket.next = anchor, anchor.next
        anchor.next.previous = bucket
        anchor.next = bucket
        return bucket

    def _remove_empty(self, bucket):
        if bucket.keys:
            return
        bucket.previous.next = bucket.next
        bucket.next.previous = bucket.previous

    def increment(self, alert_code):
        current = self.location.get(alert_code, self.head)
        target_count = current.count + 1
        target = current.next
        if target is self.tail or target.count != target_count:
            target = self._insert_after(current, target_count)
        target.keys.add(alert_code)
        self.location[alert_code] = target
        if current is not self.head:
            current.keys.remove(alert_code)
            self._remove_empty(current)

    def decrement(self, alert_code):
        current = self.location.get(alert_code)
        if current is None:
            raise KeyError(alert_code)
        if current.count == 1:
            del self.location[alert_code]
        else:
            target = current.previous
            if target is self.head or target.count != current.count - 1:
                target = self._insert_after(current.previous, current.count - 1)
            target.keys.add(alert_code)
            self.location[alert_code] = target
        current.keys.remove(alert_code)
        self._remove_empty(current)

    def minimum(self):
        return None if self.head.next is self.tail else next(iter(self.head.next.keys))

    def maximum(self):
        return None if self.tail.previous is self.head else next(iter(self.tail.previous.keys))


alerts = AlertFrequencyIndex()
for alert_code in ["dock-47", "dock-19", "dock-47", "dock-61", "dock-47", "dock-19"]:
    alerts.increment(alert_code)
print(alerts.minimum(), alerts.maximum())
alerts.decrement("dock-47")
alerts.decrement("dock-47")
print(alerts.minimum() in {"dock-47", "dock-61"}, alerts.maximum())
alerts.decrement("dock-61")
print(alerts.minimum(), alerts.maximum())

Output

dock-61 dock-47
True dock-19
dock-47 dock-19

Time, space, and tradeoff

Every operation touches one hash-map entry, at most two neighboring buckets, and constant-time set insertions or removals under usual hash-table assumptions. Increment, decrement, minimum, and maximum are therefore O(1) expected time, with O(K) space for K live keys and at most K nonempty buckets. Adversarial hash collisions can defeat that expected bound in a general hash table. Python set iteration chooses an arbitrary tied key and offers no stable ordering promise. A heap-based count index must manage stale priorities after each count change; linked adjacent buckets avoid stale records because a single update changes frequency by exactly one.

Common Mistakes

Do not retain an empty frequency bucket between its neighbors.
Do not assume an arbitrary tied key is the oldest or lexicographically smallest.
Do not decrement an absent key into a negative count.
Do not claim worst-case O(1) hashing under adversarial collisions.

Connected lessons

Compare this operation boundary with Persistent subarray ranks: subtract prefix frequency trees, Maximum-subarray segment trees: preserve the crossing burst, Li Chao interval offers: limit each line to its valid minutes, Patricia binary routing: compress chains without losing prefix matches, then complete the audit project and decision quiz.

data structures

range-query-structures