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:

  1. 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.
  2. 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.
  3. GetMaxKey() - Returns one of the keys with maximal value. If no element exists, return an empty string "".
  4. 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()
    
    

All Problems

All Solutions