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();
 */

All Problems

All Solutions