All O`one Data Structure

**All Oone Data Structure** is a classic design problem: build a container whose inc, dec, getMaxKey, and getMinKey` all run in O(1). The trick is to stop thinking in terms of a single map and start thinking in terms of buckets ordered by count.

The slow way first

The obvious design is a single dict mapping key -> count. inc and dec are easy O(1), but getMaxKey and getMinKey force you to scan every key to find the extremes — that is O(n) per call. A heap helps a little, but heaps give you log-time updates and cannot cheaply move a key whose count changed in the middle.

The question to ask: what if keys with the same count lived together, and the groups were already in sorted order? Then the smallest and largest counts are just the two ends of an ordered chain.

The idea: buckets ordered by count

Keep a doubly linked list of buckets, sorted by count ascending. Each bucket carries a count and the set of keys currently at that count. A side dict maps key -> the bucket it lives in.

• inc(key) raises the count by 1, so the key moves to the bucket one step to the right. If that bucket does not exist (or has the wrong count), splice a fresh one in first.
• dec(key) lowers the count by 1, so the key moves one step to the left (or is removed at 0).
• getMinKey reads any key from the head bucket; getMaxKey reads any key from the tail bucket. Both are O(1).

The key insight: because a single inc or dec only ever changes a count by one, a key only ever moves to an adjacent bucket — never far. That adjacency is what keeps every operation O(1).

Walk through it

Step through the animation. We inc("a") and inc("b") so both share the count=1 bucket. A second inc("a") needs a count=2 bucket — it does not exist, so we create it and slide a over. Another inc("a") builds count=3. Then dec("a") walks a back left, and finally getMin/getMax just read the two ends of the chain.

Pseudocode

buckets: doubly linked list, sorted by count ascending
keys: dict mapping key -> its bucket
 
inc(key):
    cur = keys.get(key)              # bucket key is in now (or none)
    target_count = cur.count + 1 if cur else 1
    right = cur.next if cur else head.next
    if right is missing or right.count != target_count:
        right = new bucket(target_count) spliced after cur (or head)
    right.add(key); keys[key] = right
    if cur: cur.remove(key) and unlink cur if now empty
 
dec(key):                            # mirror of inc, moving one bucket LEFT
    cur = keys[key]
    if cur.count == 1: remove key entirely
    else: move key into the bucket on the left (count - 1)
 
getMinKey(): return any key in head.next   # smallest count
getMaxKey(): return any key in tail.prev   # largest count

The Python solution

def inc(self, key):
    cur = self.keys.get(key)
    cnt = (cur.count if cur else 0) + 1
    if cur is None or cur.next.count != cnt:
        # bucket for this count is missing
        nb = Bucket(cnt)
        self.splice_after(cur or self.head, nb)
    nb = cur.next if cur else self.head.next
    nb.add(key); self.keys[key] = nb
    if cur: cur.remove(key)
 
def dec(self, key):
    cur = self.keys[key]
    cnt = cur.count - 1
    if cnt == 0:
        del self.keys[key]
    else:
        pb = cur.prev if cur.prev.count == cnt else None
        ...  # move key one bucket left
 
def getMaxKey(self):
    return self.tail.prev.any_key()
 
def getMinKey(self):
    return self.head.next.any_key()

• self.keys is the side dict mapping each key to the bucket object it currently lives in.
• In inc, cnt is the key's new count; if the right-hand neighbor does not already hold that count, we splice a fresh bucket in.
• We add the key to the new bucket and update the dict before removing it from the old one, so the dict is never stale.
• dec is the mirror image — same idea, moving one bucket to the left, deleting the key when the count would hit 0.
• getMaxKey / getMinKey simply read the bucket adjacent to the tail / head sentinel — that is the O(1) payoff of keeping the chain sorted.

Complexity

Every operation is O(1) because a count changes by exactly one, so a key only ever hops to a neighboring bucket, and the min/max are pinned to the two ends of the sorted chain.

When this pattern shows up

Practice