All O'one Data Structure — DLL of Buckets + HashMap

Problem 202 · All O'one Data Structure

Difficulty: Hard · Pattern: Doubly Linked List of Buckets + HashMap

Design: inc(key), dec(key), getMaxKey(), getMinKey() — all O(1).

Intuition

Maintain a doubly linked list of bucket nodes, each holding a frequency and a set of keys at that frequency. Two sentinel nodes (head=min, tail=max) allow O(1) access.

A key→bucket map lets us jump directly to a key's bucket.

Solutions

# Python
class Node:
    def __init__(self, freq):
        self.freq = freq
        self.keys = set()
        self.prev = self.next = None

class AllOne:
    def __init__(self):
        self.head = Node(0)  # min sentinel
        self.tail = Node(float('inf'))  # max sentinel
        self.head.next = self.tail
        self.tail.prev = self.head
        self.key_node = {}

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

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

    def inc(self, key):
        if key in self.key_node:
            node = self.key_node[key]
            freq = node.freq
            nxt = node.next
            if nxt.freq != freq + 1:
                new_node = Node(freq + 1)
                self._insert_after(node, new_node)
                nxt = new_node
            nxt.keys.add(key)
            self.key_node[key] = nxt
            node.keys.discard(key)
            if not node.keys: self._remove(node)
        else:
            nxt = self.head.next
            if nxt.freq != 1:
                new_node = Node(1)
                self._insert_after(self.head, new_node)
                nxt = new_node
            nxt.keys.add(key)
            self.key_node[key] = nxt

    def dec(self, key):
        node = self.key_node[key]
        freq = node.freq
        node.keys.discard(key)
        if freq == 1:
            del self.key_node[key]
        else:
            prev = node.prev
            if prev.freq != freq - 1:
                new_node = Node(freq - 1)
                self._insert_after(prev, new_node)
                prev = new_node
            prev.keys.add(key)
            self.key_node[key] = prev
        if not node.keys: self._remove(node)

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

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

Complexity

Time: O(1) all operations
Space: O(n) keys

Key Insight

Each bucket holds all keys with the same count. Moving a key up/down frequency is O(1) because we can insert a new bucket adjacent to the current one.