Problem description: Design a data structure to store the strings’ count with the ability to return the strings with minimum and maximum counts.
Implement the AllOne class:
AllOne() Initializes the object of the data structure.inc(String key) Increments the count of the string key by 1. If key does not exist in the data structure, insert it with count 1.dec(String key) Decrements the count of the string key by 1. If the count of key is 0 after the decrement, remove it from the data structure. It is guaranteed that key exists in the data structure before the decrement.getMaxKey() Returns one of the keys with the maximal count. If no element exists, return an empty string "".getMinKey() Returns one of the keys with the minimum count. If no element exists, return an empty string "".
Example 1:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Input ["AllOne", "inc", "inc", "getMaxKey", "getMinKey", "inc", "getMaxKey", "getMinKey"] [[], ["hello"], ["hello"], [], [], ["leet"], [], []] Output [null, null, null, "hello", "hello", null, "hello", "leet"] Explanation AllOne allOne = new AllOne(); allOne.inc("hello"); allOne.inc("hello"); allOne.getMaxKey(); // return "hello" allOne.getMinKey(); // return "hello" allOne.inc("leet"); allOne.getMaxKey(); // return "hello" allOne.getMinKey(); // return "leet"
Constraints:
1 <= key.length <= 10key consists of lowercase English letters.It is guaranteed that for each call to dec, key is existing in the data structure.
At most 5 * 104 calls will be made to inc, dec, getMaxKey, and getMinKey.
Solution: Idea is to create a doubly linked list, the list is sorted by frequency.
The node of linked list have keys that has same frequency.
Also use sentinel node head and tail to O(1) get the Max and min key.
Whenever inc or dec a key, need to check if a block exist with the new frequency. If not, create new block for it.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 class FreqNode : def __init__ (self, freq) : self.freq = freq self.words = set() self.next = None self.prev = None def insertAfter (self, prev) : self.next = prev.next self.next.prev = self prev.next = self self.prev = prev def deleteNode (self) : self.prev.next = self.next self.next.prev = self.prev self.prev = None self.next = None class AllOne : def __init__ (self) : self.head, self.tail = FreqNode(0 ), FreqNode(0 ) self.head.next = self.tail self.tail.prev = self.head self.map = {} def inc (self, key: str) -> None : if key in self.map: cur_node = self.map[key] cur_node.words.remove(key) else : cur_node = self.head if cur_node.freq+1 == cur_node.next.freq: new_node = cur_node.next else : new_node = FreqNode(cur_node.freq+1 ) new_node.insertAfter(cur_node) new_node.words.add(key) self.map[key] = new_node if not cur_node.words and cur_node.freq != 0 : cur_node.deleteNode() def dec (self, key: str) -> None : if key not in self.map: return cur_node = self.map[key] cur_node.words.remove(key) del self.map[key] if cur_node.freq-1 == cur_node.prev.freq: newNode = cur_node.prev else : newNode = FreqNode(cur_node.freq-1 ) newNode.insertAfter(cur_node.prev) newNode.words.add(key) self.map[key] = newNode if not cur_node.words: cur_node.deleteNode() def getMaxKey (self) -> str: if self.tail.prev.freq == 0 : return "" key = self.tail.prev.words.pop() self.tail.prev.words.add(key) return key def getMinKey (self) -> str: if self.head.next.freq == 0 : return "" key = self.head.next.words.pop() self.head.next.words.add(key) return key
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 class Block : def __init__ (self, val = 0 ) : self.val = val self.keys = set() self.prev = None self.next = None def remove (self) : self.prev.next = self.next self.next.prev = self.prev self.prev, self.next = None , None def insert_after (self, new_block) : old_next = self.next new_block.prev = self new_block.next = old_next old_next.prev = new_block self.next = new_block class AllOne : def __init__ (self) : self.head, self.tail = Block(), Block() self.head.next = self.tail self.tail.prev = self.head self.mapping = {} def inc (self, key: str) -> None : if key in self.mapping: block = self.mapping[key] block.keys.remove(key) else : block = self.head if block.val +1 != block.next.val: new_block = Block(block.val+1 ) block.insert_after(new_block) else : new_block = block.next new_block.keys.add(key) self.mapping[key] = new_block if not block.keys and block.val != 0 : block.remove() def dec (self, key: str) -> None : if not key in self.mapping: return block = self.mapping[key] del self.mapping[key] block.keys.remove(key) if block.val != 1 : if block.val -1 != block.prev.val: new_block = Block(block.val-1 ) block.prev.insert_after(new_block) else : new_block = block.prev new_block.keys.add(key) self.mapping[key] = new_block if not block.keys: block.remove() def getMaxKey (self) -> str: if self.tail.prev.val == 0 : return "" key = self.tail.prev.keys.pop() self.tail.prev.keys.add(key) return key def getMinKey (self) -> str: if self.head.next.val == 0 : return "" key = self.head.next.keys.pop() self.head.next.keys.add(key) return key
time complexity: $O()$