All Oone Data Structure - Leetcode Solution

The All Oone Data Structure problem on LeetCode is a design problem that asks you to implement the following data structure:

• AllOne() Initializes the data structure.
• inc(String key) Increments the count of the key by 1. If the key does not exist, insert the key with count 1.
• dec(String key) Decrements the count of the key by 1. If the key's count is 0, remove it from the data structure.
• getMaxKey() Returns one of the keys with maximal count. If no element exists, return an empty string "".
• getMinKey() Returns one of the keys with minimal count. If no element exists, return an empty string "".

To solve this problem, we can use a combination of a hash map and a doubly linked list. The hash map will store the key-value pairs, where the key is the string and the value is a node in the doubly linked list. The doubly linked list will store the keys in ascending order of their counts.

We will also keep track of two sentinel nodes in the doubly linked list: a head sentinel node and a tail sentinel node. The head sentinel node will always be less than or equal to all keys in the list, and the tail sentinel node will always be greater than or equal to all keys in the list.

Here is a detailed implementation of the All Oone Data Structure in Python:

class Node:
    def __init__(self, key):
        self.key = key
        self.count = 0
        self.prev = None
        self.next = None        

class AllOne:
    def __init__(self):
        self.key_map = {}
        self.count_map = {}
        self.head = Node('')
        self.tail = Node('')
        self.head.next = self.tail
        self.tail.prev = self.head

    def inc(self, key):
        # if the key is not in the hash map, add it to the count 1
        if key not in self.key_map:
            self.key_map[key] = Node(key)
            self.key_map[key].count = 1
            self.count_map[1] = self.count_map.get(1, []) + [self.key_map[key]]
        else:
            # increment the count of the key, and move it to the correct position in the doubly linked list
            old_count = self.key_map[key].count
            self.key_map[key].count += 1
            new_count = self.key_map[key].count

            self.count_map[old_count].remove(self.key_map[key])
            if not self.count_map[old_count]:
                del self.count_map[old_count]

            self.count_map[new_count] = self.count_map.get(new_count, []) + [self.key_map[key]]
        
        # move the key to the correct position in the doubly linked list
        self._move_to_next_pos(key)

    def dec(self, key):
        # if the key is not in the hash map, do nothing
        if key not in self.key_map:
            return
        
        # decrement the count of the key, and move it to the correct position in the doubly linked list
        old_count = self.key_map[key].count
        self.key_map[key].count -= 1
        new_count = self.key_map[key].count

        if self.key_map[key].count == 0:
            del self.key_map[key]
            self.count_map[old_count].remove(self.key_map[key])
            if not self.count_map[old_count]:
                del self.count_map[old_count]
        else:
            self.count_map[old_count].remove(self.key_map[key])
            if not self.count_map[old_count]:
                del self.count_map[old_count]

            self.count_map[new_count] = self.count_map.get(new_count, []) + [self.key_map[key]]
            self._move_to_prev_pos(key)

    def getMaxKey(self):
        # get the last node in the doubly linked list, if it's not the tail sentinel node return its key
        if self.tail.prev != self.head:
            return self.tail.prev.key
        else:
            return ""

    def getMinKey(self):
        # get the first node in the doubly linked list, if it's not the head sentinel node return its key
        if self.head.next != self.tail:
            return self.head.next.key
        else:
            return ""

    def _move_to_next_pos(self, key):
        # move the node to its next position in the doubly linked list
        node = self.key_map[key]
        count = node.count

        # if there is no next node or the next node has a different count, create a new node and insert it after the current node
        if not node.next or node.next.count != node.count+1:
            new_node = Node('')
            new_node.count = node.count + 1
            new_node.prev = node
            new_node.next = node.next
            node.next.prev = new_node
            node.next = new_node
        else:
            # otherwise just move the node to the next position
            new_node = node.next

        # update the hash map to point to the new node
        self.key_map[key] = new_node
        new_node.key = key

        # update the count map to point to the new node
        self.count_map[count].remove(node)
        if not self.count_map[count]:
            del self.count_map[count]
        self.count_map[new_node.count] = self.count_map.get(new_node.count, []) + [new_node]

    def _move_to_prev_pos(self, key):
        # move the node to its previous position in the doubly linked list
        node = self.key_map[key]
        count = node.count

        # if there is no previous node or the previous node has a different count, create a new node and insert it before the current node
        if not node.prev or node.prev.count != node.count-1:
            new_node = Node('')
            new_node.count = node.count - 1
            new_node.next = node
            new_node.prev = node.prev
            node.prev.next = new_node
            node.prev = new_node
        else:
            # otherwise just move the node to the previous position
            new_node = node.prev

        # update the hash map to point to the new node
        self.key_map[key] = new_node
        new_node.key = key

        # update the count map to point to the new node
        self.count_map[count].remove(node)
        if not self.count_map[count]:
            del self.count_map[count]
        self.count_map[new_node.count] = self.count_map.get(new_node.count, []) + [new_node]

In the _move_to_next_pos and _move_to_prev_pos methods, we are inserting new nodes into the doubly linked list if needed. We are also updating the key map and count map to point to the new nodes.

In the inc and dec methods, we are incrementing or decrementing the count of a key, and then moving it to its correct position in the doubly linked list based on its new count. If the count becomes zero, we delete the key from the hash map and count map, and remove it from the doubly linked list.

In the getMaxKey and getMinKey methods, we return the key of the first or last node in the doubly linked list if it's not the sentinel node. Otherwise, we return an empty string.

The time complexity of inc, dec, getMaxKey, and getMinKey methods is O(1), and the space complexity is O(n), where n is the number of keys in the data structure.

1