DSA The All O(1) Structure

The problem: the All O(1) spec

The All O(1) structure counts string keys and reports a key with the largest count and a key with the smallest count. Four operations define it. Inc raises one key's count by one, dec lowers it by one, get max returns any key at the largest count, and get min returns any key at the smallest count.

Every operation must run in one step, independent of how many keys the structure holds. A key whose count falls to zero leaves the structure. An empty structure answers both queries with an empty string.

script = [
    "inc(a)",
    "inc(b)",
    "inc(a)",
    "state: 1 ['b'], 2 ['a'] - max a, min b",
    "inc(b)",
    "inc(b)",
    "state: 2 ['a'], 3 ['b'] - max b, min a",
    "dec(b)",
    "dec(a)",
    "dec(a)",
    "state: 2 ['b'] - max b, min b",
]
for line in script:
    print(line)

Bucket states in the script print their keys in sorted order. Keys inside one bucket share a count, so any sorted print is a display choice, never a claim about storage order.

Intuition: one count dict, scanned per query

The first design keeps one dict from key to count. Inc and dec are single dict updates. The queries are where this design pays, because the dict holds no order by count.

A max query must inspect every count to find the largest. A min query does the same work from the other end. Each query costs a full scan of the key set.

counts = {"a": 2, "b": 5, "c": 1, "d": 5, "e": 3}
scanned = 0
best = None
for key in sorted(counts):
    scanned += 1
    if best is None or counts[key] > counts[best]:
        best = key
print("keys scanned:", scanned, "one max key:", best, "count:", counts[best])

Five keys cost five inspections for one answer. The real design groups keys by count, so the answer sits at a known end of an ordered structure and no scan happens.

Brute force: the scanning counter, counted

The naive design is the intuition, written as a class. Queries scan all keys in sorted order for determinism. A counter records the keys scanned per query.

class NaiveCounter:
    def __init__(self):
        self.counts = {}
        self.scans = 0

    def inc(self, key):
        self.counts[key] = self.counts.get(key, 0) + 1

    def dec(self, key):
        if key in self.counts:
            self.counts[key] -= 1
            if self.counts[key] == 0:
                del self.counts[key]

    def get_max(self):
        self.scans = 0
        best = ""
        for key in sorted(self.counts):
            self.scans += 1
            if best == "" or self.counts[key] > self.counts[best]:
                best = key
        return best

    def get_min(self):
        self.scans = 0
        best = ""
        for key in sorted(self.counts):
            self.scans += 1
            if best == "" or self.counts[key] < self.counts[best]:
                best = key
        return best

store = NaiveCounter()
store.inc("a")
store.inc("b")
store.inc("a")
print("max:", store.get_max(), "scanned:", store.scans)
print("min:", store.get_min(), "scanned:", store.scans)
store.inc("b")
store.inc("b")
print("max:", store.get_max(), "scanned:", store.scans)
print("min:", store.get_min(), "scanned:", store.scans)

The answers match the script. Each query scans every live key, so a store of ten thousand keys pays ten thousand inspections per query. The updates were never the problem.

The optimal solution: buckets of equal counts, ordered by count

A bucket holds every key that shares one count, and the buckets sit in order by their count, with a key map pointing each key to its current count. That ordering is the whole design.

Inc moves a key from its bucket to the next bucket up, creating that bucket when needed. Dec moves it down, and a move to zero removes the key. The smallest count is the first bucket's count and the largest is the last bucket's count, so both queries read one end directly.

class AllOne:
    def __init__(self):
        self.counts = {}
        self.buckets = {}

    def _move(self, key, old, new):
        if old in self.buckets:
            self.buckets[old].discard(key)
            if not self.buckets[old]:
                del self.buckets[old]
        if new > 0:
            self.buckets.setdefault(new, set()).add(key)
            self.counts[key] = new
        elif key in self.counts:
            del self.counts[key]

    def inc(self, key):
        old = self.counts.get(key, 0)
        self._move(key, old, old + 1)

    def dec(self, key):
        old = self.counts.get(key, 0)
        if old:
            self._move(key, old, old - 1)

    def get_max(self):
        if not self.buckets:
            return ""
        return sorted(self.buckets[max(self.buckets)])[0]

    def get_min(self):
        if not self.buckets:
            return ""
        return sorted(self.buckets[min(self.buckets)])[0]

    def show(self):
        for count in sorted(self.buckets):
            print(count, sorted(self.buckets[count]))

store = AllOne()
store.inc("a")
store.inc("b")
store.inc("a")
store.show()
print("max", store.get_max(), "min", store.get_min())
store.inc("b")
store.inc("b")
store.show()
print("max", store.get_max(), "min", store.get_min())
store.dec("b")
store.dec("a")
store.dec("a")
store.show()
print("max", store.get_max(), "min", store.get_min())

Every state matches the script from the first section. Bucket contents print sorted at each step, because the buckets themselves hold sets and a set has no promised order.

Walkthrough: the script, step by step

The walk reruns the script one operation at a time. Each row prints the buckets after the operation, in count order, with keys sorted inside each bucket.

class AllOne:
    def __init__(self):
        self.counts = {}
        self.buckets = {}

    def _move(self, key, old, new):
        if old in self.buckets:
            self.buckets[old].discard(key)
            if not self.buckets[old]:
                del self.buckets[old]
        if new > 0:
            self.buckets.setdefault(new, set()).add(key)
            self.counts[key] = new
        elif key in self.counts:
            del self.counts[key]

    def inc(self, key):
        old = self.counts.get(key, 0)
        self._move(key, old, old + 1)

    def dec(self, key):
        old = self.counts.get(key, 0)
        if old:
            self._move(key, old, old - 1)

    def get_max(self):
        if not self.buckets:
            return ""
        return sorted(self.buckets[max(self.buckets)])[0]

    def get_min(self):
        if not self.buckets:
            return ""
        return sorted(self.buckets[min(self.buckets)])[0]

    def show(self):
        for count in sorted(self.buckets):
            print(count, sorted(self.buckets[count]))

store = AllOne()
def show(action):
    state = []
    for count in sorted(store.buckets):
        state.append(str(count) + " " + str(sorted(store.buckets[count])))
    print(action, "->", "; ".join(state) if state else "empty")

store.inc("a")
show("inc(a)")
store.inc("b")
show("inc(b)")
store.inc("a")
show("inc(a)")
store.inc("b")
show("inc(b)")
store.inc("b")
show("inc(b)")
store.dec("b")
show("dec(b)")
store.dec("a")
show("dec(a)")
store.dec("a")
show("dec(a)")
print("final max:", store.get_max(), "final min:", store.get_min())

The middle rows show buckets being born and dying. Count 1 vanishes when its last key climbs, and count 3 appears when b climbs into it. No bucket ever holds a stale key, because every move removes before it adds.

Complexity

Inc and dec move one key between neighbouring buckets, a fixed set of dict and set operations, so their time is O(1). Get max and get min read one end bucket and sort its keys only for display in this article, so the query itself is O(1), and the space is O(k) for k live keys.

for keys in [10, 100, 1000]:
    print("live keys", keys, "- naive scans per query:", keys, " bucket end reads per query: 1")

The naive column grows with the store. The bucket column does not move, and that flat count is the O(1) the name promises.

Edge cases and pitfalls

Decrementing a missing key does nothing. Decrementing a key at count 1 removes it from the structure entirely. Querying an empty structure returns the empty string from both ends.

The determinism pitfall is printing a bucket raw. A set prints in hash order, which can differ between runs. Every print in this article sorts the bucket first, and get max and get min return the first key of the sorted bucket so repeated runs agree.

class AllOne:
    def __init__(self):
        self.counts = {}
        self.buckets = {}

    def _move(self, key, old, new):
        if old in self.buckets:
            self.buckets[old].discard(key)
            if not self.buckets[old]:
                del self.buckets[old]
        if new > 0:
            self.buckets.setdefault(new, set()).add(key)
            self.counts[key] = new
        elif key in self.counts:
            del self.counts[key]

    def inc(self, key):
        old = self.counts.get(key, 0)
        self._move(key, old, old + 1)

    def dec(self, key):
        old = self.counts.get(key, 0)
        if old:
            self._move(key, old, old - 1)

    def get_max(self):
        if not self.buckets:
            return ""
        return sorted(self.buckets[max(self.buckets)])[0]

    def get_min(self):
        if not self.buckets:
            return ""
        return sorted(self.buckets[min(self.buckets)])[0]

    def show(self):
        for count in sorted(self.buckets):
            print(count, sorted(self.buckets[count]))

store = AllOne()
print("empty max:", repr(store.get_max()), "empty min:", repr(store.get_min()))
store.dec("ghost")
print("after dec of a missing key, buckets:", store.buckets)
store.inc("x")
store.dec("x")
print("after inc then dec of x, buckets:", store.buckets, "counts:", store.counts)
store.inc("b")
store.inc("a")
store.inc("a")
store.show()
print("max:", store.get_max(), "min:", store.get_min())
store.dec("a")
store.dec("a")
store.show()
print("max:", store.get_max(), "min:", store.get_min())

The last rows show a key leaving by decrement alone. Once a reaches zero it is gone from both the counts and the buckets, and b answers both queries.