Strict O(1), similar as LFU Cache, two HashMap + one double linked list + sentinel node trick


  • 0
    public class AllOne {
        
        Map<Integer, ValNode> valMap = new HashMap<>();
        Map<String, Node> keyMap = new HashMap<>();
        ValNode valDummy = new ValNode(0);
        
        private boolean isEmpty() {
            return valDummy.next==valDummy && valDummy.prev==valDummy;
        }
        
        class ValNode {
            ValNode prev, next;
            Node keyDummy;
            int val;
            ValNode(int _val) {
                val = _val;
                keyDummy = new Node("");
                prev = this;
                next = this;
            }
            public boolean isEmpty() {
                return keyDummy.next==keyDummy && keyDummy.prev==keyDummy;
            }
        }
    
        class Node {
            Node prev, next;
            String key;
            int value;
            Node(String _key) {
                key = _key;
                value = 1;
                prev = this;
                next = this;
            }
        }
        
        private void unlink(ValNode node) {
            node.next.prev = node.prev;
            node.prev.next = node.next;
            valMap.remove(node.val);
        }
        
        private void link(ValNode preNode, ValNode node) {
            preNode.next.prev = node;
            node.next = preNode.next;
            preNode.next = node;
            node.prev = preNode;
            valMap.put(node.val, node);
        }
        
        private void unlink(Node node) {
            node.next.prev = node.prev;
            node.prev.next = node.next;
            keyMap.remove(node.key);
        }
        
        private void link(Node preNode, Node node) {
            preNode.next.prev = node;
            node.next = preNode.next;
            preNode.next = node;
            node.prev = preNode;
            keyMap.put(node.key, node);
        }
        
        // The node must be already linked
        private void incVal(Node node) {
            ValNode valNode = valMap.get(node.value);
            unlink(node);
            node.value++;
            if(!valMap.containsKey(node.value)) {
                ValNode newValNode = new ValNode(node.value);
                link(valNode.prev, newValNode);
            }
            link(valMap.get(node.value).keyDummy, node);
            if(valNode.isEmpty())
                unlink(valNode);
        }
        
        // The node must be already linked
        private void decVal(Node node) {
            ValNode valNode = valMap.get(node.value);
            unlink(node);
            node.value--;
            if(node.value==0) {
                if(valNode.isEmpty())
                    unlink(valNode);
                return;
            }
            if(!valMap.containsKey(node.value)) {
                ValNode newValNode = new ValNode(node.value);
                link(valNode, newValNode);
            }
            link(valMap.get(node.value).keyDummy, node);
            if(valNode.isEmpty())
                unlink(valNode);
        }
    
        /** Initialize your data structure here. */
        public AllOne() {}
        
        /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
        public void inc(String key) {
            if(!keyMap.containsKey(key)) {
                Node node = new Node(key);
                if(!valMap.containsKey(node.value)) {
                    ValNode newValNode = new ValNode(node.value);
                    link(valDummy.prev, newValNode); // link to end of val chain
                }
                link(valMap.get(node.value).keyDummy, node);
            } else
                incVal(keyMap.get(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(keyMap.containsKey(key))
                decVal(keyMap.get(key));
        }
        
        /** Returns one of the keys with maximal value. */
        public String getMaxKey() {
            return isEmpty() ? "" : valDummy.next.keyDummy.next.key;
        }
        
        /** Returns one of the keys with Minimal value. */
        public String getMinKey() {
            return isEmpty() ? "" : valDummy.prev.keyDummy.next.key;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.