All O'one Data Structure: O(1) Inc, Dec, Max, Min

LeetCode 432: All O'one Data Structure asks you to design a data structure that tracks string keys and their integer counts. You need four operations, all in O(1) time: inc(key) to increment a key's count, dec(key) to decrement it, getMaxKey() to return any key with the highest count, and getMinKey() to return any key with the lowest count. If that sounds like it should be impossible, you are not alone. The trick is a clever pairing of a hash map with a doubly linked list of "count buckets."

Why this problem matters

This problem is a natural extension of the hash-map-plus-linked-list pattern you see in LRU Cache. In LRU Cache, the linked list tracks recency order. Here, the linked list tracks count order. The same structural idea, just a different invariant to maintain.

The real challenge is keeping everything O(1). A naive approach might store counts in a hash map and scan for the max or min when needed. That gives O(1) for inc and dec but O(n) for getMaxKey and getMinKey. To get all four operations down to O(1), you need the linked list to always be sorted by count, with the min at one end and the max at the other. The trick is that you never need to "sort" the list. When a key's count changes by 1, it only ever moves to the immediately adjacent bucket.

This problem also teaches you an important design principle: when your data has a natural ordering that only changes by small increments, a doubly linked list with neighbor-aware updates can maintain that ordering in constant time. You will see this same idea in LFU Cache (LeetCode 460) and other frequency-tracking problems.

The approach

The data structure has two parts:

1. A hash map (key_to_bucket) that maps each string key to the bucket node containing it. This gives O(1) access to any key's current bucket.
2. A doubly linked list of bucket nodes, where each node holds a count and a set of keys with that count. The list stays sorted by count, with the smallest count at the head end and the largest at the tail end.

Each bucket node stores:

• count: the integer count for all keys in this bucket
• keys: a set of string keys that currently have this count
• prev and next: pointers to neighboring buckets

For inc(key), you find the key's current bucket (or create a count=1 bucket if the key is new), remove the key from that bucket, and add it to the bucket with count+1. If no bucket with count+1 exists, you create one and insert it right after the current bucket. If the old bucket is now empty, you remove it from the list.

For dec(key), the logic is symmetric. Move the key to the bucket with count-1, creating it if needed. If the count drops to 0, remove the key entirely.

For getMaxKey(), return any key from the last real bucket in the list (the one closest to the tail sentinel). For getMinKey(), return any key from the first real bucket (closest to the head sentinel). Both are O(1) because you just follow one pointer.

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

class AllOne:
    def __init__(self):
        self.head = Bucket(0)
        self.tail = Bucket(0)
        self.head.next = self.tail
        self.tail.prev = self.head
        self.key_to_bucket = {}

    def _insert_after(self, node, new_node):
        new_node.prev = node
        new_node.next = node.next
        node.next.prev = new_node
        node.next = new_node

    def _remove_bucket(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def inc(self, key):
        if key in self.key_to_bucket:
            cur = self.key_to_bucket[key]
            new_count = cur.count + 1
            if cur.next.count != new_count:
                new_bucket = Bucket(new_count)
                self._insert_after(cur, new_bucket)
            cur.next.keys.add(key)
            self.key_to_bucket[key] = cur.next
            cur.keys.discard(key)
            if not cur.keys:
                self._remove_bucket(cur)
        else:
            if self.head.next.count != 1:
                new_bucket = Bucket(1)
                self._insert_after(self.head, new_bucket)
            self.head.next.keys.add(key)
            self.key_to_bucket[key] = self.head.next

    def dec(self, key):
        cur = self.key_to_bucket[key]
        new_count = cur.count - 1
        if new_count == 0:
            del self.key_to_bucket[key]
        else:
            if cur.prev.count != new_count:
                new_bucket = Bucket(new_count)
                self._insert_after(cur.prev, new_bucket)
            cur.prev.keys.add(key)
            self.key_to_bucket[key] = cur.prev
        cur.keys.discard(key)
        if not cur.keys:
            self._remove_bucket(cur)

    def getMaxKey(self):
        if self.tail.prev == self.head:
            return ""
        return next(iter(self.tail.prev.keys))

    def getMinKey(self):
        if self.head.next == self.tail:
            return ""
        return next(iter(self.head.next.keys))

Step-by-step walkthrough

Let's trace through a sequence of operations: inc("a"), inc("b"), inc("a"), inc("b"), inc("a"), getMaxKey(), getMinKey(). Watch how keys move between buckets as their counts change, and how empty buckets get cleaned up automatically.

Notice the pattern: every inc or dec moves a key to an adjacent bucket. Because the list is sorted by count and counts only change by 1, the target bucket is always the immediate neighbor. You never need to search or traverse the list. That is why every operation stays O(1).

Complexity analysis

Time: O(1) per operation. Every inc and dec does a constant number of hash map lookups, set operations, and linked list pointer updates. getMaxKey and getMinKey each follow a single pointer.

Space: O(n) where n is the number of distinct keys. The hash map stores one entry per key. The linked list has at most n bucket nodes (one per distinct count value, bounded by the number of keys).

Edge cases to watch for

• Decrementing a key with count 1. The key should be removed entirely from the data structure, not moved to a count=0 bucket. Make sure you delete it from the hash map.
• Multiple keys in the same bucket. When getMaxKey or getMinKey is called, any key from the bucket is valid. Use next(iter(bucket.keys)) to grab one without caring which.
• All keys have the same count. The linked list has a single bucket. Both getMaxKey and getMinKey return keys from that same bucket, which is correct since all counts are equal.
• Empty data structure. After decrementing the last key, the list should only contain the sentinel nodes. getMaxKey and getMinKey should return empty strings.
• Incrementing a key that already exists vs. a new key. These are two distinct code paths. A new key always enters the count=1 bucket. An existing key moves from its current bucket to count+1.

The building blocks

This problem combines two fundamental building blocks that you will see over and over in design problems:

Hash map for O(1) key lookup. The key_to_bucket map is the same pattern as the key_to_node map in LRU Cache. It gives you instant access to a key's position in the linked list, which is what makes list operations O(1) instead of O(n). If you had to search the list for a key, the whole design falls apart. You can study this pattern in depth in Data Structure: Hash Maps.

Doubly linked list for O(1) ordered insertion and removal. The bucket list is the same structure as the node list in LRU Cache, just with a different invariant. Instead of tracking recency, it tracks count order. The sentinel nodes (head and tail) eliminate boundary checks, and the doubly linked pointers let you insert or remove any node in constant time. For a deeper look at linked list mechanics, see Data Structure: Linked Lists.

From understanding to recall

The All O'one Data Structure has more moving parts than most design problems. Two helper methods for list manipulation, the bucket creation and cleanup logic in inc and dec, the sentinel pattern, and the hash map connecting keys to their buckets. You can read this solution and understand every line right now, but reproducing it from memory in a week is a different challenge entirely. The details matter: do you insert the new bucket after the current one or before it? When do you clean up empty buckets? What happens when you decrement to zero?

Spaced repetition is how you lock in these details. Write the full solution from scratch, then do it again in two days, then again in five. After a few reps, the bucket creation logic and the inc/dec symmetry become automatic. That is the gap between "I understand this" and "I can write this cold."

Related posts

• LRU Cache - The classic hash map + doubly linked list design problem that this solution extends
• Min Stack - Another design problem where auxiliary data structures provide O(1) access to aggregate information
• Implement Trie - A different design problem that builds a tree-shaped data structure for string operations