Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/432.html
432. All O`one Data Structure
Level
Hard
Description
Implement a data structure supporting the following operations:
- Inc(Key) - Inserts a new key with value 1. Or increments an existing key by 1. Key is guaranteed to be a non-empty string.
- Dec(Key) - If Key’s value is 1, remove it from the data structure. Otherwise decrements an existing key by 1. If the key does not exist, this function does nothing. Key is guaranteed to be a non-empty string.
- GetMaxKey() - Returns one of the keys with maximal value. If no element exists, return an empty string
""
. - GetMinKey() - Returns one of the keys with minimal value. If no element exists, return an empty string
""
.
Challenge: Perform all these in O(1) time complexity.
Solution
To do all the operations in O(1) time complexity, create a class DoublyLinkedNode
, which contains a value, a set of all keys that have the value, the previous node and the next node. In class AllOne
, maintain the head and the tail of the doubly-linked list, where the node with the minimum value is after the head and the node with the maximum value is before the tail. Also maintain two maps. The first map stores each key and the corresponding value. The second map stores each value and the node of the value.
For the constructor, initialize the two maps and initialize the head node and the tail node to have value -1 and head.next = tail
and tail.prev = head
.
For method inc
, there are two cases. If the key already exists, update the value and update the maps the corresponding nodes. Otherwise, create a new node with value 1 and the current key.
For method dec
, only consider the case when the key exists. The case is similar to inc
, but the case when the value is decreased to 0 needs to be considered individually.
For method getMaxKey
, obtain the node just before the tail, and return any key in the node’s set. If the list is empty, return an empty string.
For method getMinKey
, obtain the node just after the head, and return any key in the node’s set. If the list is empty, return an empty string.
-
class AllOne { Map<String, Integer> keyValueMap; Map<Integer, DoublyLinkedNode> valueNodeMap; DoublyLinkedNode head; DoublyLinkedNode tail; /** Initialize your data structure here. */ public AllOne() { keyValueMap = new HashMap<String, Integer>(); valueNodeMap = new HashMap<Integer, DoublyLinkedNode>(); head = new DoublyLinkedNode(); tail = new DoublyLinkedNode(); head.next = tail; tail.prev = head; } /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */ public void inc(String key) { if (keyValueMap.containsKey(key)) { int value = keyValueMap.get(key); int newValue = value + 1; keyValueMap.put(key, newValue); DoublyLinkedNode node = valueNodeMap.get(value); DoublyLinkedNode prev = node.prev, next = node.next; node.keySet.remove(key); if (node.keySet.isEmpty()) { prev.next = next; next.prev = prev; valueNodeMap.remove(value); } if (next.value == node.value + 1) next.keySet.add(key); else { DoublyLinkedNode newNode = new DoublyLinkedNode(newValue, key); valueNodeMap.put(newValue, newNode); prev = next.prev; prev.next = newNode; next.prev = newNode; newNode.prev = prev; newNode.next = next; } } else { keyValueMap.put(key, 1); DoublyLinkedNode node = valueNodeMap.get(1); if (node == null) { node = new DoublyLinkedNode(1, key); valueNodeMap.put(1, node); DoublyLinkedNode prevNext = head.next; head.next = node; prevNext.prev = node; node.prev = head; node.next = prevNext; } else node.keySet.add(key); } } /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */ public void dec(String key) { if (keyValueMap.containsKey(key)) { int value = keyValueMap.get(key); int newValue = value - 1; if (newValue > 0) keyValueMap.put(key, newValue); else keyValueMap.remove(key); DoublyLinkedNode node = valueNodeMap.get(value); DoublyLinkedNode prev = node.prev, next = node.next; node.keySet.remove(key); if (node.keySet.isEmpty()) { prev.next = next; next.prev = prev; valueNodeMap.remove(value); } if (prev.value == node.value - 1) prev.keySet.add(key); else if (newValue > 0) { DoublyLinkedNode newNode = new DoublyLinkedNode(newValue, key); valueNodeMap.put(newValue, newNode); next = prev.next; prev.next = newNode; next.prev = newNode; newNode.prev = prev; newNode.next = next; } } } /** Returns one of the keys with maximal value. */ public String getMaxKey() { if (tail.prev == head) return ""; else return tail.prev.keySet.iterator().next(); } /** Returns one of the keys with Minimal value. */ public String getMinKey() { if (head.next == tail) return ""; else return head.next.keySet.iterator().next(); } } class DoublyLinkedNode { int value; Set<String> keySet; DoublyLinkedNode prev; DoublyLinkedNode next; public DoublyLinkedNode() { this(0); } public DoublyLinkedNode(int value) { this.value = value; this.keySet = new HashSet<String>(); } public DoublyLinkedNode(int value, String key) { this.value = value; this.keySet = new HashSet<String>(); keySet.add(key); } } /** * 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(); */ ############ 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(); */
-
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() ############ class List(object): @staticmethod def delete(elem): elem.prev.next = elem.next elem.next.prev = elem.prev elem.next = elem.prev = None return elem @staticmethod def move(elem, newPrev, newNext): elem.prev = newPrev elem.next = newNext newPrev.next = elem newNext.prev = elem @staticmethod def append(head, elem): List.move(elem, head.prev, head) @staticmethod def insertAfter(head, elem): List.move(elem, head, head.next) @staticmethod def isEmpty(head): return head.next == head.prev == head @staticmethod def initHead(head): head.prev = head.next = head class Node(object): def __init__(self, val): self.val = val self.prev = None self.next = None self.keys = set() def add(self, key): self.keys |= {key} def remove(self, key): self.keys -= {key} def isEmpty(self): return len(self.keys) == 0 def peepKey(self): for k in self.keys: return k return "" class AllOne(object): def __init__(self): """ Initialize your data structure here. """ self.d = {} self.head = Node(-1) List.initHead(self.head) def inc(self, key): """ Inserts a new key <Key> with value 1. Or increments an existing key by 1. :type key: str :rtype: void """ head = self.head if key not in self.d: if head.next.val == 1: self.d[key] = head.next self.d[key].add(key) else: newNode = Node(1) newNode.add(key) List.insertAfter(head, newNode) self.d[key] = newNode else: node = self.d[key] newNode = None if node.next.val != node.val + 1: newNode = Node(node.val + 1) newNode.add(key) List.insertAfter(node, newNode) else: newNode = node.next newNode.add(key) node.remove(key) if node.isEmpty(): List.delete(node) del self.d[key] self.d[key] = newNode def dec(self, key): """ Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. :type key: str :rtype: void """ if key not in self.d: return head = self.head node = self.d[key] if node.val == 1: node.remove(key) if node.isEmpty(): List.delete(node) del self.d[key] else: newNode = None if node.prev.val != node.val - 1: newNode = Node(node.val - 1) newNode.add(key) List.insertAfter(node.prev, newNode) else: newNode = node.prev newNode.add(key) node.remove(key) if node.isEmpty(): List.delete(node) del self.d[key] self.d[key] = newNode def getMaxKey(self): """ Returns one of the keys with maximal value. :rtype: str """ return self.head.prev.peepKey() def getMinKey(self): """ Returns one of the keys with Minimal value. :rtype: str """ return self.head.next.peepKey() # 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()