432. All O`one Data Structure

09/18/2021

Leetcode

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 "".

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.

Basic Idea:

这道题目和LFU Cache有些类似，要实现 O(1) 的时间复杂度，可以使用一个doubly linked list来维持每个freq的顺序，当count +1 或者 -1 的时候，将key从原本freq对应的node中挪到前面或者后面的node中。Min和Max可以在head和tail中得到。和LFU那道题不同的是，这里不需要在相同freq的node之间实现LRU，逻辑上稍微简单一些。

Java Code:

class AllOne {
    private static class Node {
        int count;
        Node prev;
        Node next;
        Set<String> keys = new HashSet<>();
        
        public Node(int count) {
            this.count = count;
        }
    }
    
    private Node head;
    private Node tail;
    private Map<Integer, Node> countNodeMap = new HashMap<>();
    private Map<String, Integer> countKeyMap = new HashMap<>();
    
    /** Initialize your data structure here. */
    public AllOne() {
        head = new Node(0);
        tail = new Node(-1);
        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 (!countKeyMap.containsKey(key)) {
            // 如果之前不存在，则插到最前面count=1的node中
            ensureExistNext(head);
            head.next.keys.add(key);
            countKeyMap.put(key, 1);
        } else {
            // 如果存在，则删掉旧的，加入old count+1 的node中
            int prevCount = countKeyMap.get(key);
            Node prevNode = countNodeMap.get(prevCount);
            ensureExistNext(prevNode);
            prevNode.next.keys.add(key);
            prevNode.keys.remove(key);
            if (prevNode.keys.isEmpty()) {
                deleteNode(prevNode);
            }
            countKeyMap.put(key, prevCount + 1);
        }
    }
    
    /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
    public void dec(String key) {
        int prevCount = countKeyMap.get(key);
        Node prevNode = countNodeMap.get(prevCount);
        if (prevCount > 1) {
            ensureExistPrev(prevNode);
            prevNode.prev.keys.add(key);
            countKeyMap.put(key, prevCount - 1);
        } else {
            // 如果减为0，则需要删掉key
            countKeyMap.remove(key);
        }
        prevNode.keys.remove(key);
        if (prevNode.keys.isEmpty()) {
            deleteNode(prevNode);
        }
    }
    
    /** Returns one of the keys with maximal value. */
    public String getMaxKey() {
        if (head.next == tail) {
            return "";
        }
        return tail.prev.keys.iterator().next();
    }
    
    /** Returns one of the keys with Minimal value. */
    public String getMinKey() {
        if (head.next == tail) {
            return "";
        }
        return head.next.keys.iterator().next();
    }
    
    // ensure previous node with count curr.count-1 exist
    private void ensureExistPrev(Node curr) {
        if (curr.prev == head || curr.prev.count != curr.count - 1) {
            Node newNode = new Node(curr.count - 1);
            newNode.next = curr;
            newNode.prev = curr.prev;
            curr.prev.next = newNode;
            curr.prev = newNode;
            countNodeMap.put(newNode.count, newNode);
        }
    }
    
    // ensure next node with count curr.count+1 exist
    private void ensureExistNext(Node curr) {
        if (curr.next == tail 
            || curr.next.count != curr.count + 1) {
            Node newNode = new Node(curr.count + 1);
            newNode.next = curr.next;
            newNode.prev = curr;
            curr.next.prev = newNode;
            curr.next = newNode;
            countNodeMap.put(newNode.count, newNode);
        }
    }
    
    private void deleteNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
        countNodeMap.remove(node.count);
    }
}

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