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.

Java
Python

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

432 - All O`one Data Structure

432. All O`one Data Structure

Level

Description

Solution

All Problems

All Solutions

Welcome to Subscribe On Youtube

432. All O`one Data Structure

Level

Description

Solution

All Problems

All Solutions