432.All_Oone_Data_Structure(Hard).md

432. All O`one Data Structure (Hard)

Date and Time: Jun 18, 2026, 12:00 (EST)

Link: https://leetcode.com/problems/all-oone-data-structure/

Question:

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() Initializes 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 maximal count. If no element exists, return an empty string "".

• String getMinKey() Returns one of the keys with the minimum count. If no element exists, return an empty string "".

Note that each function must run in O(1) average time complexity.

Example 1:

Input: ["AllOne", "inc", "inc", "getMaxKey", "getMinKey", "inc", "getMaxKey", "getMinKey"]
[[], ["hello"], ["hello"], [], [], ["leet"], [], []]

Output: [null, null, null, "hello", "hello", null, "hello", "leet"]

Explanation:
AllOne allOne = new AllOne();
allOne.inc("hello");
allOne.inc("hello");
allOne.getMaxKey(); // return "hello"
allOne.getMinKey(); // return "hello"
allOne.inc("leet");
allOne.getMaxKey(); // return "hello"
allOne.getMinKey(); // return "leet"

Constraints:

• 1 <= key.length <= 10

• key consists of lowercase English letters.

• It is guaranteed that for each call to dec, key is existing in the data structure.

• At most 5 * 10^4 calls will be made to inc, dec, getMaxKey, and getMinKey.

Walk-through:

Use a doubly linked list where each node holds a frequency and a set of all keys at that frequency. Two dummy nodes left and right serve as sentinels (left = min end, right = max end). A hashmap {key: node} tracks which node each key lives in.

insert(node, newNode) — inserts newNode immediately after node.

delete(node) — unlinks node from the list and clears its pointers.

inc(key):

1. If key exists in hashmap, look at node.next. If it doesn't exist or has the wrong frequency (node.frequency + 1), create a new node there.
2. Add key to node.next.val, update hashmap[key], remove key from old node, delete old node if empty.
3. If key doesn't exist, check if left.next has frequency == 1; if not, create a new node. Add key there.

dec(key):

1. If frequency > 1, look at node.prev. If it doesn't exist or has the wrong frequency (node.frequency - 1), create a new node there.
2. Move key to node.prev, remove from old node, delete old node if empty.
3. If frequency == 1, remove key from the node and from hashmap; delete node if empty.

getMaxKey() — return any key from right.prev.val.

getMinKey() — return any key from left.next.val.

Python Solution:

class Node:
    def __init__(self):
        self.prev, self.next = None, None
        self.frequency, self.keyStore = 0, set()

class AllOne:
    
    # Save string with their counts
    # Linked list to hold all strings with their counts
    # Min key on the left, max key on the right
    # Each node holds one count, all the strings with the same cnt will be saved in the same node
    # SC: O(n)
    def __init__(self):
        self.hashmap = {}   # {key: node}
        self.left, self.right = Node(), Node()
        self.left.next, self.right.prev = self.right, self.left

    def insert(self, node, newNode):
        left, right = node, node.next
        left.next, right.prev = newNode, newNode
        newNode.prev, newNode.next = left, right

    def delete(self, node):
        left, right = node.prev, node.next
        left.next, right.prev = right, left

    # 1. Check if key exists
    # 2. Promote: move key from current node to next node, remember to check if next node exists
    def inc(self, key: str) -> None:
        if key in self.hashmap:
            node = self.hashmap[key]
            # Check if next frequency+1 node exists
            if node.next.frequency == node.frequency+1:
                # Add into next frequency node and remove from current node
                node.next.keyStore.add(key)
                self.hashmap[key] = node.next
                # Remove from current node
                node.keyStore.remove(key)
                if len(node.keyStore) == 0:
                    self.delete(node)
            # Else, we create new node
            else:
                newNode = Node()
                newNode.frequency = node.frequency + 1
                newNode.keyStore.add(key)
                # Insert new node into linked list
                self.insert(node, newNode)
                self.hashmap[key] = newNode
                # Remove key from old node
                node.keyStore.remove(key)
                if len(node.keyStore) == 0:
                    self.delete(node)
        # Initialize key to frequency = 1 node
        else:
            # Check if frequency = 1 node exists
            if self.left.next.frequency == 1:
                self.left.next.keyStore.add(key)
                self.hashmap[key] = self.left.next
            else:
                newNode = Node()
                newNode.frequency = 1
                newNode.keyStore.add(key)
                self.insert(self.left, newNode)
                self.hashmap[key] = newNode
        
    # 1. Move down the key to the prev node
    # 2. Remember to check if frequency-1 node exists
    def dec(self, key: str) -> None:
        node = self.hashmap[key]
        # Check if key in frequency = 1 node
        if node.frequency == 1:
            node.keyStore.remove(key)
            del self.hashmap[key]
            if not node.keyStore:
                self.delete(node)
        else:
            # Move it to frequency - 1 node
            if node.prev.frequency == node.frequency-1:
                newNode = node.prev
                newNode.keyStore.add(key)
                self.hashmap[key] = newNode
            # Need to create frequency - 1 node
            else:
                newNode = Node()
                newNode.frequency = node.frequency - 1
                newNode.keyStore.add(key)
                self.hashmap[key] = newNode
                self.insert(node.prev, newNode)
            # Remove from oldNode
            node.keyStore.remove(key)
            # Check if oldNode needs to be deleted
            if len(node.keyStore) == 0:
                self.delete(node)
        
    # Get right node.prev
    def getMaxKey(self) -> str:
        if self.right.prev == self.left:
            return ""
        else:
            for val in self.right.prev.keyStore:
                return val
        
    # Get left node.next
    def getMinKey(self) -> str:
        if self.left.next == self.right:
            return ""
        else:
            for val in self.left.next.keyStore:
                return val


# Your AllOne object will be instantiated and called as such:
# obj = AllOne()
# obj.inc(key)
# obj.dec(key)
# param_3 = obj.getMaxKey()
# param_4 = obj.getMinKey()

Time Complexity: $O(1)$ for all operations.
Space Complexity: $O(n)$, where n is the total number of unique keys.