#432

All O`one Data Structure

candidate master · 1590 · lc hard +32 · 44.2% accepted · 2,224 likes · top 26%

Description

Design a data structure that tracks how many times each string key has been counted, and can retrieve any key with the maximum or minimum count in constant time.

Implement the AllOne class:

- AllOne() Initializes an empty instance.

- inc(String key) Increments key's count by 1; inserts it with count 1 if it does not exist.

- dec(String key) Decrements key's count by 1; removes it when the count reaches 0. The key is guaranteed to exist.

- getMaxKey() Returns any key with the largest count, or "" if empty.

- getMinKey() Returns any key with the smallest count, or "" if empty.

All operations must run in O(1) amortized time.

Example 1:

Input

["AllOne", "inc", "inc", "getMaxKey", "getMinKey", "inc", "getMaxKey", "getMinKey"]

[[], ["hello"], ["hello"], [], [], ["leet"], [], []]

Output

[null, null, null, "hello", "hello", null, "hello", "leet"]

Example 2:

Explanation

AllOne allOne = new AllOne();

allOne.inc("hello");

allOne.getMaxKey(); // return "hello"

allOne.getMinKey(); // return "hello"

allOne.inc("leet");

allOne.getMaxKey(); // return "hello"

allOne.getMinKey(); // return "leet"

Code

class AllOne:

    def __init__(self):
        

    def inc(self, key: str) -> None:
        

    def dec(self, key: str) -> None:
        

    def getMaxKey(self) -> str:
        

    def getMinKey(self) -> str:
        


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

class AllOne:

    def __init__(self):
        

    def inc(self, key: str) -> None:
        

    def dec(self, key: str) -> None:
        

    def getMaxKey(self) -> str:
        

    def getMinKey(self) -> str:
        


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