LeetCode 0432. All O`one Data Structure Solution in Java, Python, C++, JavaScript, Go & Rust | Explanation + Code

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 "".

Note that each function must run in O(1) average time complexity.

 

Example 1:

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 <= 10
• key 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.

Solutions

Solution 1

PythonJava

class Node: def __init__(self, key='', cnt=0): self.prev = None self.next = None self.cnt = cnt self.keys = {key} def insert(self, node): node.prev = self node.next = self.next node.prev.next = node node.next.prev = node return node def remove(self): self.prev.next = self.next self.next.prev = self.prev class AllOne: def __init__(self): self.root = Node() self.root.next = self.root self.root.prev = self.root self.nodes = {} def inc(self, key: str) -> None: root, nodes = self.root, self.nodes if key not in nodes: if root.next == root or root.next.cnt > 1: nodes[key] = root.insert(Node(key, 1)) else: root.next.keys.add(key) nodes[key] = root.next else: curr = nodes[key] next = curr.next if next == root or next.cnt > curr.cnt + 1: nodes[key] = curr.insert(Node(key, curr.cnt + 1)) else: next.keys.add(key) nodes[key] = next curr.keys.discard(key) if not curr.keys: curr.remove() def dec(self, key: str) -> None: root, nodes = self.root, self.nodes curr = nodes[key] if curr.cnt == 1: nodes.pop(key) else: prev = curr.prev if prev == root or prev.cnt < curr.cnt - 1: nodes[key] = prev.insert(Node(key, curr.cnt - 1)) else: prev.keys.add(key) nodes[key] = prev curr.keys.discard(key) if not curr.keys: curr.remove() def getMaxKey(self) -> str: return next(iter(self.root.prev.keys)) def getMinKey(self) -> str: return next(iter(self.root.next.keys)) # 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()(code-box)

class AllOne { Node root = new Node(); Map<String, Node> nodes = new HashMap<>(); public AllOne() { root.next = root; root.prev = root; } public void inc(String key) { if (!nodes.containsKey(key)) { if (root.next == root || root.next.cnt > 1) { nodes.put(key, root.insert(new Node(key, 1))); } else { root.next.keys.add(key); nodes.put(key, root.next); } } else { Node curr = nodes.get(key); Node next = curr.next; if (next == root || next.cnt > curr.cnt + 1) { nodes.put(key, curr.insert(new Node(key, curr.cnt + 1))); } else { next.keys.add(key); nodes.put(key, next); } curr.keys.remove(key); if (curr.keys.isEmpty()) { curr.remove(); } } } public void dec(String key) { Node curr = nodes.get(key); if (curr.cnt == 1) { nodes.remove(key); } else { Node prev = curr.prev; if (prev == root || prev.cnt < curr.cnt - 1) { nodes.put(key, prev.insert(new Node(key, curr.cnt - 1))); } else { prev.keys.add(key); nodes.put(key, prev); } } curr.keys.remove(key); if (curr.keys.isEmpty()) { curr.remove(); } } public String getMaxKey() { return root.prev.keys.iterator().next(); } public String getMinKey() { return root.next.keys.iterator().next(); } } class Node { Node prev; Node next; int cnt; Set<String> keys = new HashSet<>(); public Node() { this("", 0); } public Node(String key, int cnt) { this.cnt = cnt; keys.add(key); } public Node insert(Node node) { node.prev = this; node.next = this.next; node.prev.next = node; node.next.prev = node; return node; } public void remove() { this.prev.next = this.next; this.next.prev = this.prev; } } /** * Your AllOne object will be instantiated and called as such: * AllOne obj = new AllOne(); * obj.inc(key); * obj.dec(key); * String param_3 = obj.getMaxKey(); * String param_4 = obj.getMinKey(); */(code-box)