All O'one Data Structure — O(1) Min and Max via Doubly Linked Frequency Buckets

Problem Statement#

Design a data structure to store the strings' count with the ability to return the strings with minimum and maximum counts.

Implement the AllOne class:

• AllOne() Initialises the object of the data structure.
• void inc(String key) Increments the count of the string key by 1. If key does not exist in the data structure, insert it with count 1.
• void dec(String key) Decrements the count of the string key by 1. If the count of key is 0 after the decrement, remove it from the data structure. It is guaranteed that key exists in the data structure before the decrement.
• String getMaxKey() Returns one of the keys with the maximum count. If no element exists, returns "".
• String getMinKey() Returns one of the keys with the minimum count. If no element exists, returns "".

All functions must run in O(1) average time complexity.

Constraints:

• 1 <= key.length <= 10
• key consists of lowercase English letters.
• At most 5 × 10^4 calls will be made to inc, dec, getMaxKey, and getMinKey.
• It is guaranteed that when calling dec, the key exists and its count ≥ 1.

Examples:

AllOne allOne = new AllOne();
allOne.inc("hello");     // count: {hello:1}
allOne.inc("hello");     // count: {hello:2}
allOne.getMaxKey();      // returns "hello"
allOne.getMinKey();      // returns "hello"
allOne.inc("leet");      // count: {hello:2, leet:1}
allOne.getMaxKey();      // returns "hello"
allOne.getMinKey();      // returns "leet"

Why This Problem Matters#

All O'one Data Structure is the hardest hash map design problem in the standard interview canon. It requires simultaneously maintaining min and max in O(1) — something a heap can do in O(log n), but O(1) requires a much more creative design.

The problem appears at Google and Amazon for senior and staff engineer roles because it tests whether candidates can design for O(1) amortised complexity when naive approaches (sorted dict, heap) give O(log n). The doubly linked list of frequency buckets is one of the most elegant designs in competitive programming, and understanding it deeply reveals mastery of both data structure composition and amortised analysis.

The core insight — that "moving a key from frequency bucket f to f±1" is an O(1) pointer manipulation in a doubly linked list — mirrors techniques used in real cache implementations, database buffer management, and streaming frequency estimation.

This problem also tests your ability to handle edge cases in pointer manipulation: what happens when the target bucket doesn't exist yet? What happens when a bucket becomes empty after removal? Both require careful handling of sentinels and null checks.

The Core Insight#

Maintain a doubly linked list of bucket nodes, where each bucket holds:

• A frequency value (the count for all keys in this bucket).
• A set of keys currently at that frequency.
• Pointers to the previous and next buckets.

Two sentinel nodes (head with frequency 0, tail with frequency infinity) bracket the list. This means:

• The node after head is always the minimum-frequency bucket (if non-empty).
• The node before tail is always the maximum-frequency bucket (if non-empty).

getMinKey(): Return any key from head.next.keys. getMaxKey(): Return any key from tail.prev.keys.

A key_to_node hash map maps each key to its current bucket node. This enables O(1) jump to a key's bucket without traversing the list.

inc(key) algorithm:

• If key exists: move it from bucket b to bucket b+1. If b+1 doesn't exist, create it and insert it after b.
• If key is new: insert it into the frequency-1 bucket. If that bucket doesn't exist, create it after head.
• If the old bucket is now empty, remove it from the list.

dec(key) algorithm:

• Move key from bucket b to bucket b-1. If b-1 = 0, remove the key entirely.
• If b-1 != 0 and the bucket doesn't exist, create it before b.
• If the old bucket is now empty, remove it.

Visual Dry Run#

Initial state: head(0) <-> tail(inf)

Solution (Optimal)#

class Node:
    """Frequency bucket node in the doubly linked list."""
    def __init__(self, freq: int):
        self.freq = freq
        self.keys: set = set()
        self.prev: 'Node' = None
        self.next: 'Node' = None
 
class AllOne:
    def __init__(self):
        # Sentinel nodes: head = min side, tail = max side
        self.head = Node(0)
        self.tail = Node(float('inf'))
        self.head.next = self.tail
        self.tail.prev = self.head
        # Maps each key to its current bucket node
        self.key_node: dict = {}
 
    def _insert_after(self, node: Node, new_node: Node) -> None:
        """Insert new_node immediately after node."""
        new_node.prev = node
        new_node.next = node.next
        node.next.prev = new_node
        node.next = new_node
 
    def _remove_node(self, node: Node) -> None:
        """Remove node from the doubly linked list."""
        node.prev.next = node.next
        node.next.prev = node.prev
 
    def inc(self, key: str) -> None:
        if key in self.key_node:
            node = self.key_node[key]
            freq = node.freq
            next_node = node.next
            # Ensure the next node has freq+1
            if next_node.freq != freq + 1:
                new_node = Node(freq + 1)
                self._insert_after(node, new_node)
                next_node = new_node
            next_node.keys.add(key)
            self.key_node[key] = next_node
            node.keys.discard(key)
            if not node.keys:
                self._remove_node(node)
        else:
            # New key: goes into frequency-1 bucket
            first = self.head.next
            if first.freq != 1:
                new_node = Node(1)
                self._insert_after(self.head, new_node)
                first = new_node
            first.keys.add(key)
            self.key_node[key] = first
 
    def dec(self, key: str) -> None:
        node = self.key_node[key]
        freq = node.freq
        node.keys.discard(key)
 
        if freq == 1:
            # Key's count drops to 0: remove it entirely
            del self.key_node[key]
        else:
            prev_node = node.prev
            # Ensure the prev node has freq-1
            if prev_node.freq != freq - 1:
                new_node = Node(freq - 1)
                self._insert_after(prev_node, new_node)
                prev_node = new_node
            prev_node.keys.add(key)
            self.key_node[key] = prev_node
 
        # Remove the old bucket if empty
        if not node.keys:
            self._remove_node(node)
 
    def getMaxKey(self) -> str:
        if self.tail.prev == self.head:
            return ""
        return next(iter(self.tail.prev.keys))
 
    def getMinKey(self) -> str:
        if self.head.next == self.tail:
            return ""
        return next(iter(self.head.next.keys))

class AllOne {
    constructor() {
        // Use a Map as an ordered doubly linked list: node = {freq, keys, prev, next}
        this.head = { freq: 0, keys: new Set(), prev: null, next: null };
        this.tail = { freq: Infinity, keys: new Set(), prev: null, next: null };
        this.head.next = this.tail;
        this.tail.prev = this.head;
        this.keyNode = new Map(); // key -> bucket node
    }
 
    _insertAfter(node, newNode) {
        newNode.prev = node;
        newNode.next = node.next;
        node.next.prev = newNode;
        node.next = newNode;
    }
 
    _removeNode(node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
 
    inc(key) {
        if (this.keyNode.has(key)) {
            const node = this.keyNode.get(key);
            const freq = node.freq;
            let next = node.next;
            if (next.freq !== freq + 1) {
                const newNode = { freq: freq + 1, keys: new Set(), prev: null, next: null };
                this._insertAfter(node, newNode);
                next = newNode;
            }
            next.keys.add(key);
            this.keyNode.set(key, next);
            node.keys.delete(key);
            if (node.keys.size === 0) this._removeNode(node);
        } else {
            let first = this.head.next;
            if (first.freq !== 1) {
                const newNode = { freq: 1, keys: new Set(), prev: null, next: null };
                this._insertAfter(this.head, newNode);
                first = newNode;
            }
            first.keys.add(key);
            this.keyNode.set(key, first);
        }
    }
 
    dec(key) {
        const node = this.keyNode.get(key);
        const freq = node.freq;
        node.keys.delete(key);
 
        if (freq === 1) {
            this.keyNode.delete(key);
        } else {
            let prev = node.prev;
            if (prev.freq !== freq - 1) {
                const newNode = { freq: freq - 1, keys: new Set(), prev: null, next: null };
                this._insertAfter(prev, newNode);
                prev = newNode;
            }
            prev.keys.add(key);
            this.keyNode.set(key, prev);
        }
 
        if (node.keys.size === 0) this._removeNode(node);
    }
 
    getMaxKey() {
        return this.tail.prev === this.head ? "" : [...this.tail.prev.keys][0];
    }
 
    getMinKey() {
        return this.head.next === this.tail ? "" : [...this.head.next.keys][0];
    }
}

Complexity Analysis:

• Time: O(1) amortised for all operations. Each key moves at most one bucket per inc/dec call; creating and removing bucket nodes is O(1) pointer manipulation.
• Space: O(n) where n = number of distinct keys.

Common Mistakes#

• Not using sentinel nodes: Without head and tail sentinels, every operation requires null checks for list boundaries. Sentinels simplify the code dramatically.
• Not creating a new bucket when needed: If node.next.freq != freq + 1, a new bucket must be created. Forgetting this corrupts the sorted order of the list.
• Removing a key from key_node when count hits 0 but not from the bucket: Both key_node and node.keys must be updated.
• Returning a key from an empty bucket at head/tail: Always check head.next != tail in getMinKey and tail.prev != head in getMaxKey.
• Python's set iteration order: next(iter(some_set)) gives an arbitrary element, not the LRU one. The problem only requires returning "any" key at the max/min frequency, so this is fine.

Follow-up Questions#

1. How does this design compare to a heap-based approach? (Heap gives O(log n) for inc/dec. This design achieves O(1) by exploiting the structured nature of frequency changes — keys move exactly one bucket up or down.)
2. Can you modify this to also support getKeyWithFreq(f) in O(1)? (Yes — the key_node map allows direct access to any key's bucket.)
3. What if you need getTopK(k) — the k keys with highest counts? (Traverse from tail backwards. O(k) time.)
4. How would you handle concurrent access to this data structure? (Read-write locks per bucket for fine-grained locking, or a single global lock for simplicity.)
5. How is this design related to the LFU Cache? (LFU Cache uses the same bucket structure; the additional complexity in LFU is within-bucket LRU ordering and eviction logic.)
6. What real-world systems use this pattern? (Stream processing systems for real-time leaderboards, frequency-based routing in load balancers, hotspot detection in databases.)

Related Problems#

• [LC 432] All O'one Data Structure — this exact problem.
• [LC 460] LFU Cache — uses the same bucket structure with added eviction logic.
• [LC 146] LRU Cache — simpler O(1) cache design; a good prerequisite.
• [LC 706] Design HashMap — foundational hash map design.
• [LC 895] Maximum Frequency Stack — frequency-based stack with O(1) pop of max-frequency element.
• [LC 716] Max Stack — O(1) max retrieval from a stack, related design challenge.

Key Takeaways#

• All O'one Data Structure (LC 432) achieves O(1) min and max using a doubly linked list of frequency buckets with sentinel head and tail nodes.
• Each key is stored in exactly one frequency bucket and can be found in O(1) via the key_to_node hash map.
• Keys move exactly one bucket per inc/dec call — this is the property that makes O(1) achievable.
• Always create a new bucket when the adjacent bucket does not have the required frequency; always remove an empty bucket immediately.
• head.next is always the minimum-frequency bucket; tail.prev is always the maximum-frequency bucket.
• Sentinel nodes eliminate all boundary null checks, making the code dramatically simpler and less error-prone.
• The same bucket-linked-list pattern underlies LFU Cache (LC 460) — understanding this problem makes LFU significantly easier to implement.