LeetCode Solutions Blog

All O`one Data Structure

Difficulty: Hard

Problem Description

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 with methods to increment and decrement counts, and to get the keys with maximum and minimum counts.

Key Insights

The data structure must support efficient insertion, deletion, and retrieval operations.
Each operation (inc, dec, getMaxKey, getMinKey) must run in O(1) average time complexity.
Maintaining a mapping of counts to keys is essential to efficiently track keys with minimum and maximum counts.
A doubly linked list can be employed to maintain the order of keys based on their counts.

Space and Time Complexity

Time Complexity: O(1) for all operations (average case)
Space Complexity: O(N), where N is the number of unique keys stored in the data structure.

Solution

The AllOne class utilizes a combination of a hash table and a doubly linked list to efficiently manage the counts of strings. The hash table maps each string to its current count, while the linked list maintains the order of counts. When a count is incremented or decremented, the corresponding node in the linked list is updated or rearranged accordingly. The head of the linked list represents the minimum count, and the tail represents the maximum count, allowing for O(1) retrieval of these keys.

Code Solutions

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

class AllOne:
    def __init__(self):
        self.key_count = {}
        self.count_node = {}
        self.head = Node(0)  # Dummy head
        self.tail = Node(0)  # Dummy tail
        self.head.next = self.tail
        self.tail.prev = self.head

    def _add_node(self, new_node, prev_node):
        new_node.prev = prev_node
        new_node.next = prev_node.next
        prev_node.next.prev = new_node
        prev_node.next = new_node

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

    def inc(self, key: str) -> None:
        if key in self.key_count:
            self.key_count[key] += 1
            count = self.key_count[key]
            current_node = self.count_node[count - 1]
            if count not in self.count_node:
                new_node = Node(count)
                self.count_node[count] = new_node
                self._add_node(new_node, current_node)
            self.count_node[count].keys.add(key)
            current_node.keys.remove(key)
            if not current_node.keys:
                self._remove_node(current_node)
        else:
            self.key_count[key] = 1
            if 1 not in self.count_node:
                new_node = Node(1)
                self.count_node[1] = new_node
                self._add_node(new_node, self.head)
            self.count_node[1].keys.add(key)

    def dec(self, key: str) -> None:
        count = self.key_count[key]
        current_node = self.count_node[count]
        current_node.keys.remove(key)
        if not current_node.keys:
            self._remove_node(current_node)
            del self.count_node[count]
        self.key_count[key] -= 1
        if self.key_count[key] == 0:
            del self.key_count[key]
        else:
            new_count = self.key_count[key]
            if new_count not in self.count_node:
                new_node = Node(new_count)
                self.count_node[new_count] = new_node
                self._add_node(new_node, current_node.prev)
            self.count_node[new_count].keys.add(key)

    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))