LeetCode Solutions Blog

All O`one Data Structure

Number: 432

Difficulty: Hard

Paid? No

Problem Description

Design a data structure that supports incrementing and decrementing the count of strings and can return one string with the maximum count and one with the minimum count, all in O(1) average time per operation. The data structure must support the functions inc(key), dec(key), getMaxKey(), and getMinKey().

Key Insights

Use a Doubly-Linked List (DLL) where each node holds a unique count value and a set of keys with that count.
Maintain a Hash Map (keyToNode) to quickly locate the node corresponding to each key.
Insert new nodes in the DLL when a key’s count is incremented or decremented and the adjacent node does not have the target count.
Remove nodes from the DLL when no keys remain in that count.
The head of the DLL holds the minimum count and the tail holds the maximum count.

Space and Time Complexity

Time Complexity: O(1) average for inc, dec, getMaxKey, and getMinKey. Space Complexity: O(n) where n is the number of unique keys in the data structure.

Solution

The solution uses a combination of a doubly-linked list and hash maps. Each node in the DLL represents a frequency and maintains a set of keys that have that frequency. A hash map maps keys to their corresponding node. When inc(key) or dec(key) is called, we update the key’s frequency and move the key to the appropriate node in the DLL. If the adjacent node with the required frequency doesn’t exist, we create a new node and insert it in the correct position. Removal of a key from a node and deletion of empty nodes ensures that getMinKey() and getMaxKey() can be returned directly from the head and tail of the DLL.

Code Solutions

# Node class to represent a frequency bucket in the doubly linked list
class Node:
    def __init__(self, count):
        self.count = count                 # frequency count for keys in this node
        self.keys = set()                  # set of keys with this frequency
        self.prev = None                   # previous node in the linked list
        self.next = None                   # next node in the linked list

class AllOne:
    def __init__(self):
        # Use sentinel nodes for easier handling of edge cases.
        self.head = Node(float('-inf'))
        self.tail = Node(float('inf'))
        self.head.next = self.tail
        self.tail.prev = self.head
        # Map each key to its corresponding node.
        self.keyToNode = {}

    # Helper: insert newNode after prevNode in the linked list.
    def _insertNodeAfter(self, prevNode, newNode):
        newNode.prev = prevNode
        newNode.next = prevNode.next
        prevNode.next.prev = newNode
        prevNode.next = newNode

    # Helper: remove a node if it has no keys.
    def _removeNode(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def inc(self, key: str) -> None:
        # If key is new, treat current node as head.
        if key not in self.keyToNode:
            curr = self.head
        else:
            curr = self.keyToNode[key]
            curr.keys.remove(key)
        # Check if the next node has count = current count + 1.
        targetCount = (0 if curr == self.head else curr.count) + 1
        if curr.next == self.tail or curr.next.count != targetCount:
            # Create new node with targetCount.
            newNode = Node(targetCount)
            self._insertNodeAfter(curr, newNode)
        else:
            newNode = curr.next
        newNode.keys.add(key)
        self.keyToNode[key] = newNode
        # Remove the current node if it is not a sentinel and has no keys.
        if curr != self.head and len(curr.keys) == 0:
            self._removeNode(curr)

    def dec(self, key: str) -> None:
        curr = self.keyToNode[key]
        curr.keys.remove(key)
        # If decrementing causes the count to be 0, remove key completely.
        if curr.count == 1:
            del self.keyToNode[key]
        else:
            targetCount = curr.count - 1
            # Check if the previous node has the target count.
            if curr.prev == self.head or curr.prev.count != targetCount:
                newNode = Node(targetCount)
                # Insert newNode before current.
                self._insertNodeAfter(curr.prev, newNode)
            else:
                newNode = curr.prev
            newNode.keys.add(key)
            self.keyToNode[key] = newNode
        # Clean up current node if empty.
        if len(curr.keys) == 0:
            self._removeNode(curr)

    def getMaxKey(self) -> str:
        # The node before tail has the maximal count.
        return next(iter(self.tail.prev.keys)) if self.tail.prev != self.head else ""

    def getMinKey(self) -> str:
        # The node after head has the minimal count.
        return next(iter(self.head.next.keys)) if self.head.next != self.tail else ""
        
# Example usage:
# obj = AllOne()
# obj.inc("hello")
# obj.inc("hello")
# print(obj.getMaxKey())  # "hello"
# print(obj.getMinKey())  # "hello"
# obj.inc("leet")
# print(obj.getMaxKey())  # "hello"
# print(obj.getMinKey())  # "leet"