Solution: All O`one Data Structure

Statement▼

Design a data structure that tracks the frequency of string keys and allows for efficient updates and queries.

Implement the AllOne class with these methods:

Constructor: Initializes the data structure.
inc(String key): Increases the count of the given key by $1$ . If the key is absent, insert it with a count of $1$ .
dec(String key): Decreases the count of the given key by $1$ . If the count becomes $0$ after decrementing, remove the key entirely. The assumption is that the key exists when this function is called.
getMaxKey(): Returns any one key with the highest count. If the data structure is empty, return an empty string.
getMinKey(): Returns any one key with the lowest count. If the data structure is empty, return an empty string.

Note: All operations must be performed in average $O(1)$ time complexity.

Constraints:

⋮

Tap here to switch tabs

Problem

Submissions

Solution

Design a data structure that tracks the frequency of string keys and allows for efficient updates and queries.

Implement the AllOne class with these methods:

Constructor: Initializes the data structure.
inc(String key): Increases the count of the given key by $1$ . If the key is absent, insert it with a count of $1$ .
dec(String key): Decreases the count of the given key by $1$ . If the count becomes $0$ after decrementing, remove the key entirely. The assumption is that the key exists when this function is called.
getMaxKey(): Returns any one key with the highest count. If the data structure is empty, return an empty string.
getMinKey(): Returns any one key with the lowest count. If the data structure is empty, return an empty string.

Note: All operations must be performed in average $O(1)$ time complexity.

Constraints: