Welcome to Subscribe On Youtube

432. All O`one Data Structure

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

  • 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()
    
    

All Problems

All Solutions