Implement a data structure supporting the following operations:



Inc(Key) - Inserts a new key  with value 1. Or increments an existing key by 1. Key is guaranteed to be a non-empty string.
Dec(Key) - If Key's value is 1, remove it from the data structure. Otherwise decrements an existing key by 1. If the key does not exist, this function does nothing. Key is guaranteed to be a non-empty string.
GetMaxKey() - Returns one of the keys with maximal value. If no element exists, return an empty string "".
GetMinKey() - Returns one of the keys with minimal value. If no element exists, return an empty string "".




Challenge: Perform all these in O(1) time complexity.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Data structures

Starter code: class AllOne:
    def __init__(self):
        """
        Initialize your data structure here.
        """
    def inc(self, key: str) -> None:
        """
        Inserts a new key <key> with value 1. Or increments an existing key by 1.
        """
    def dec(self, key: str) -> None:
        """
        Decrements an existing key by 1. If Key's value is 1, remove it from the data structure.
        """
    def getMaxKey(self) -> str:
        """
        Returns one of the keys with maximal value.
        """
    def getMinKey(self) -> str:
        """
        Returns one of the keys with Minimal value.
        """
# 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()</key>

Solutions: