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:

• $1 \leq$ key.length $\leq 10$

• key consists only of lowercase English letters.

• It is guaranteed that each call to dec is made with a key that exists in the data structure.

• At most $5 \times 10^2$ calls will be made to inc, dec, getMaxKey, and getMinKey.

Solution

We use a combination of a doubly linked list and two hash maps to efficiently track and retrieve keys with the highest and lowest frequencies in constant time. The linked list organizes nodes by frequency in increasing order, each holding a set of keys with that frequency. One hash map maps each key to its frequency, and the other maps each frequency to its corresponding node. This setup allows us to increment and decrement key frequencies, and quickly move keys between nodes, while maintaining direct access to the min and max frequency nodes through the list’s head and tail. By carefully managing the node list and hash maps, all operations—inc, dec, getMaxKey, and getMinKey—achieve $O(1)$ time complexity.

First, define a custom doubly linked list node class, Node, to store:

1. A frequency (count).

2. A set of keys (keys) that share the same frequency.

3. Pointers to the previous and next nodes in the list.

The data members in the AllOne data structure are defined as:

1. A hash map, keyCount, mapping each key to its frequency.

2. A hash map, countNode, mapping a frequency to its corresponding node in the linked list.

3. A dummy head node.

4. A dummy tail node.

Constructor:

1. To simplify edge handling, initialize the head and tail nodes with sentinel values (INT_MIN and INT_MAX).

2. Set head.next to tail and tail.prev to head to link the two dummy nodes.

inc(key):

To handle inc(key) (increment the count of a key by 1):

1. Increment keyCount[key] and retrieve the previous count in cnt.

2. Retrieve the current node, curr, for cnt from countNode (if cnt > 0); otherwise, set curr to NULL.

3. Check if a node for count cnt + 1 already exists:

   1. If yes, use it as nextNode.

   2. If not, insert a new node with count cnt + 1 after curr (or after head if curr is NULL) using the insertNodeAfter() helper and store it in nextNode.

4. Insert the key into nextNode.keys.

5. If curr exists:

   1. Remove the key from curr.keys.

   2. If curr.keys becomes empty, remove curr from the list using the removeNode() helper.

dec(key):

To handle dec(key) (decrement the count of key by 1):

1. Retrieve the current count, cnt, of the key.

2. Retrieve the current node, curr, from countNode.

3. Decrement the key’s count in keyCount.

4. If the key’s new count becomes 0, remove it from keyCount.

5. If the key still exists:

   1. Check if a node for cnt - 1 exists:

      1. If yes, use it as prevNode.

      2. If not, insert a new node with count cnt - 1 before curr using insertNodeAfter() and store it in prevNode.

   2. Insert the key into prevNode.keys.

6. Remove the key from curr.keys.

7. If curr.keys becomes empty, delete curr using removeNode().

getMaxKey():

1. Return one of the keys from the node just before the dummy tail (i.e., with the highest frequency).

2. If no keys exist, return an empty string.

getMinKey():

1. Return one of the keys from the node just after the dummy head (i.e., with the lowest frequency).

2. If no keys exist, return an empty string.

The insertNodeAfter() helper function inserts a new node with frequency cnt after a given node curr.

1. Create a new node newNode with count = cnt.

2. Set the prev and next pointers of newNode as newNode.prev = curr and newNode.next = curr.next.

3. Update the neighboring nodes to include newNode in the list as curr.next.prev = newNode and curr.next = newNode.

4. Add newNode to the countNode map using cnt as the key.

5. Return newNode.

The removeNode() helper function removes node from the doubly linked list and cleans up the hash map.

1. Update adjacent nodes’ previous and next pointers to bypass node: as node.prev.next = node.next and node.next.prev = nodeprev.

2. Remove the node’s entry from the countNode map using node.count.

3. Deallocate the node’s memory.

Let’s look at the following illustration to get a better understanding of the solution: