All O'one Data Structure

Table of Contents +

This is one of the hardest design questions out there. Every single operation must be O(1), including finding the key with the highest count and the key with the lowest count. Min and max in constant time is what makes people sweat. The structure you pick is everything here.

🎯 The Problem

You build a structure that tracks counts of string keys. It supports four operations.

The operations:

inc(key) adds one to a key’s count. A new key starts at 1.
dec(key) removes one from a key’s count. If the count hits 0, the key is removed.
getMaxKey() returns any key with the highest count.
getMinKey() returns any key with the lowest count.

The constraints:

Every operation must run in O(1). That is the whole challenge.
If the structure is empty, both getMaxKey and getMinKey return an empty string.

inc("a")        -> counts: a=1
inc("b")        -> counts: a=1, b=1
inc("b")        -> counts: a=1, b=2
getMaxKey()     -> "b"   (b has the highest count, 2)
getMinKey()     -> "a"   (a has the lowest count, 1)
dec("b")        -> counts: a=1, b=1
getMaxKey()     -> "a" or "b"   (both have count 1)
dec("a")        -> a removed; counts: b=1
getMinKey()     -> "b"   (only b is left)

So after the last dec("a"), the key a is gone, and b is both the max and the min.

Here is how the counts change as the operations run.

🐢 Approach 1: Plain Hash Map of Counts (Brute Force)

The idea in one line: keep one map from key to count, and search it when you need the min or max.

The idea:

One hash map. The key maps to its count.
inc and dec just change the number.

How it works:

inc adds one to the stored count.
dec lowers it, and removes the key at zero.
getMaxKey and getMinKey scan every key to find the highest or lowest count.

Why it is weak:

The scan to find min or max is O(n), where n is the number of keys.
So two of the four operations break the O(1) rule.
The plain map has no ordering by count to lean on.

Here is the plain-hash-map code:

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

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

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

    def getMaxKey(self):
        return max(self.counts, key=self.counts.get) if self.counts else ""

    def getMinKey(self):
        return min(self.counts, key=self.counts.get) if self.counts else ""

⚡ Approach 2: Doubly Linked List of Buckets (Best)

The idea in one line: group keys into buckets by count, keep the buckets in order, and the min and max are always at the two ends.

The idea:

A doubly linked list is a chain of nodes. Each node points to the next and the previous one.
Each node is a bucket. A bucket holds one count and the set of keys at that count.
Keep the buckets sorted by count, smallest at the front, largest at the back.
Keep a hash map from each key to the bucket it lives in.

How getMin and getMax work:

getMinKey reads any key from the first bucket.
getMaxKey reads any key from the last bucket.
No search at all. We only look at the two ends.

How inc and dec work:

inc moves the key to the bucket for count plus one. If that bucket is missing, create and link it in. Remove the key from the old bucket. Unlink the old bucket if it is empty.
dec is the mirror toward count minus one. At count 0 the key just leaves.
The map points straight at each key’s bucket, so we never search the list.

Why it is fast:

Linking or unlinking a node fixes only a few pointers, so it is O(1).
Moving a key between neighbor buckets is O(1).
So every one of the four operations stays O(1).

Here is the bucket list with the key-to-bucket map after inc("a"), inc("b"), inc("b").

Steps to Solve

Make a bucket node with a count and a set of keys. Link buckets in a doubly linked list, sorted by count.
Keep two guard nodes, a head and a tail, so the ends are always there.
Keep a hash map from key to the bucket that holds it.
For inc, find the key’s bucket. The target is the next bucket if its count is one more, else a new bucket inserted after.
Move the key into the target bucket, update the map, and remove it from the old bucket. Unlink the old bucket if it is empty.
For dec, do the mirror toward the previous bucket. If the new count is 0, drop the key and the map entry.
For getMaxKey, return any key from the bucket before the tail. For getMinKey, return any key from the bucket after the head. Return an empty string if no buckets exist.

[data-tabs] [role="tablist"], [data-tabs] [data-scroll] { display: none !important; } [data-tabs] [role="tabpanel"] { display: block !important; } [data-tabs] [role="tabpanel"] + [role="tabpanel"] { margin-top: 1rem; }

This Python version builds the doubly linked list of buckets by hand, with head and tail guard nodes.

class Bucket:
    def __init__(self, count):
        self.count = count
        self.keys = set()      # keys with this count
        self.prev = None
        self.next = None


class AllOne:
    def __init__(self):
        self.head = Bucket(0)  # guard at the low end
        self.tail = Bucket(0)  # guard at the high end
        self.head.next = self.tail
        self.tail.prev = self.head
        self.key_bucket = {}   # key -> its bucket

    def _insert_after(self, node, count):
        b = Bucket(count)              # link a new bucket in
        b.prev, b.next = node, node.next
        node.next.prev = b
        node.next = b
        return b

    def _remove(self, node):
        node.prev.next = node.next     # unlink an empty bucket
        node.next.prev = node.prev

    def inc(self, key):
        if key not in self.key_bucket:
            first = self.head.next
            if first is self.tail or first.count != 1:
                first = self._insert_after(self.head, 1)
            first.keys.add(key)
            self.key_bucket[key] = first
            return
        cur = self.key_bucket[key]
        nxt = cur.next
        if nxt is self.tail or nxt.count != cur.count + 1:
            nxt = self._insert_after(cur, cur.count + 1)
        nxt.keys.add(key)
        self.key_bucket[key] = nxt
        cur.keys.remove(key)
        if not cur.keys:
            self._remove(cur)

    def dec(self, key):
        if key not in self.key_bucket:
            return
        cur = self.key_bucket[key]
        if cur.count == 1:                  # drops to 0, remove key
            del self.key_bucket[key]
            cur.keys.remove(key)
            if not cur.keys:
                self._remove(cur)
            return
        prv = cur.prev
        if prv is self.head or prv.count != cur.count - 1:
            prv = self._insert_after(cur.prev, cur.count - 1)
        prv.keys.add(key)
        self.key_bucket[key] = prv
        cur.keys.remove(key)
        if not cur.keys:
            self._remove(cur)

    def get_max_key(self):
        if self.tail.prev is self.head:
            return ""
        return min(self.tail.prev.keys)   # any key works; min keeps it stable

    def get_min_key(self):
        if self.head.next is self.tail:
            return ""
        return min(self.head.next.keys)   # any key works; min keeps it stable


a = AllOne()
a.inc("a")
a.inc("b")
a.inc("b")
print("getMaxKey() ->", a.get_max_key())
print("getMinKey() ->", a.get_min_key())
a.dec("b")
print("getMaxKey() ->", a.get_max_key())
a.dec("a")
print("getMinKey() ->", a.get_min_key())

The output of the above code will be:

getMaxKey() -> b
getMinKey() -> a
getMaxKey() -> a
getMinKey() -> b

Let us walk through the Python inc method line by line, because moving a key between buckets is the core idea.

    def inc(self, key):
        if key not in self.key_bucket:
            first = self.head.next
            if first is self.tail or first.count != 1:
                first = self._insert_after(self.head, 1)
            first.keys.add(key)
            self.key_bucket[key] = first
            return
        cur = self.key_bucket[key]
        nxt = cur.next
        if nxt is self.tail or nxt.count != cur.count + 1:
            nxt = self._insert_after(cur, cur.count + 1)
        nxt.keys.add(key)
        self.key_bucket[key] = nxt
        cur.keys.remove(key)
        if not cur.keys:
            self._remove(cur)

The line if key not in self.key_bucket checks if the key is brand new. A new key needs count 1. The line first = self.head.next looks at the very first bucket, right after the head guard.

The line if first is self.tail or first.count != 1 asks if there is no count-1 bucket yet. If the first bucket is the tail guard, the list is empty. If its count is not 1, the smallest count is higher than 1. Either way we call self._insert_after(self.head, 1) to make a fresh count-1 bucket at the front. Then we add the key and record its bucket in the map.

For a key that already exists, the line cur = self.key_bucket[key] finds its current bucket in O(1) using the map. We never search the list. The map points straight at it.

The line nxt = cur.next looks at the next bucket, the one with a higher count. The line if nxt is self.tail or nxt.count != cur.count + 1 checks if a bucket for count plus one already sits there. If not, we insert one with self._insert_after(cur, cur.count + 1).

The line nxt.keys.add(key) moves the key into that higher bucket, and we update the map. Then cur.keys.remove(key) takes it out of the old bucket. Finally if not cur.keys: self._remove(cur) unlinks the old bucket when it is empty. Every step here touches only a few pointers and one set, so it all stays O(1).

⏱️ Time and Space Complexity

The plain hash map makes inc and dec O(1) but min and max O(n), because finding them means scanning every key. The bucket list keeps counts in order, so the smallest and largest are at the two ends. That makes all four operations O(1). The cost is a more involved structure and the memory for the buckets and the map. Space is proportional to the number of keys plus the number of distinct counts.

Approach	inc / dec	getMaxKey / getMinKey	Space
Plain hash map of counts	O(1)	O(n)	O(n)
Doubly linked list of buckets	O(1)	O(1)	O(n)

Tip

When a problem demands O(1) for both updates and finding the min or max, think buckets in a sorted linked list. Group items by their key value, keep the groups in order, and the answer is always at one of the two ends.

🧩 Key Takeaways

✅ A plain count map cannot do min and max in O(1), because it must scan all keys.
✅ Group keys into buckets by count, and keep the buckets sorted in a doubly linked list.
✅ The smallest count is at the front and the largest at the back, so min and max are O(1).
✅ A hash map from key to bucket finds any key’s bucket instantly, so inc and dec are O(1).
✅ Moving a key means linking it to a neighbor bucket and unlinking the old one if empty.

Check Your Knowledge

4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

🚀 What’s Next?

Insert Delete GetRandom O(1)
Design Hit Counter

Previous Snapshot Array Next Design Tic-Tac-Toe

All O'one Data Structure

Follow Us

Follow Us