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
keyby1 . If the key is absent, insert it with a count of1 .dec(String key): Decreases the count of the given
keyby1 . If the count becomes0 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≤ key.length≤10 keyconsists only of lowercase English letters.It is guaranteed that each call to
decis made with a key that exists in the data structure.At most
5×102 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
First, define a custom doubly linked list node class, Node, to store:
A frequency (
count).A set of keys (
keys) that share the same frequency.Pointers to the previous and next nodes in the list.
The data members in the AllOne data structure are defined as:
A hash map,
keyCount, mapping each key to its frequency.A hash map,
countNode, mapping a frequency to its corresponding node in the linked list.A dummy
headnode.A dummy
tailnode.
Constructor:
To simplify edge handling, initialize the head and tail nodes with sentinel values (
INT_MINandINT_MAX).Set
head.nexttotailandtail.prevtoheadto link the two dummy nodes.
inc(key):
To handle inc(key) (increment the count of a key by 1):
Increment
keyCount[key]and retrieve the previous count incnt.Retrieve the current node,
curr, forcntfromcountNode(ifcnt > 0); otherwise, setcurrto NULL.Check if a node for count
cnt + 1already exists:If yes, use it as
nextNode.If not, insert a new node with count
cnt + 1aftercurr(or afterheadifcurris NULL) using theinsertNodeAfter()helper and store it innextNode.
Insert the key into
nextNode.keys.If
currexists:Remove the key from
curr.keys.If
curr.keysbecomes empty, removecurrfrom the list using theremoveNode()helper.
dec(key):
To handle dec(key) (decrement the count of key by 1):
Retrieve the current count,
cnt, of thekey.Retrieve the current node,
curr, fromcountNode.Decrement the
key’s count inkeyCount.If the
key’s new count becomes0, remove it fromkeyCount.If the key still exists:
Check if a node for
cnt - 1exists:If yes, use it as
prevNode.If not, insert a new node with count
cnt - 1beforecurrusinginsertNodeAfter()and store it inprevNode.
Insert the key into
prevNode.keys.
Remove the key from
curr.keys.If
curr.keysbecomes empty, deletecurrusingremoveNode().
getMaxKey():
Return one of the keys from the node just before the dummy
tail(i.e., with the highest frequency).If no keys exist, return an empty string.
getMinKey():
Return one of the keys from the node just after the dummy
head(i.e., with the lowest frequency).If no keys exist, return an empty string.
The insertNodeAfter() helper function inserts a new node with frequency cnt after a given node curr.
Create a new node
newNodewithcount = cnt.Set the
prevandnextpointers ofnewNodeasnewNode.prev = currandnewNode.next = curr.next.Update the neighboring nodes to include
newNodein the list ascurr.next.prev = newNodeandcurr.next = newNode.Add
newNodeto thecountNodemap usingcntas the key.Return
newNode.
The removeNode() helper function removes node from the doubly linked list and cleans up the hash map.
Update adjacent nodes’ previous and next pointers to bypass
node: asnode.prev.next = node.nextandnode.next.prev = nodeprev.Remove the node’s entry from the
countNodemap usingnode.count.Deallocate the
node’s memory.
Let’s look at the following illustration to get a better understanding of the solution: