Java AC all strict O(1) not average O(1), easy to read


  • 28
    A

    Main idea is to maintain a list of Bucket's, each Bucket contains all keys with the same count.

    1. head and tail can ensure both getMaxKey() and getMaxKey() be done in O(1).
    2. keyCountMap maintains the count of keys, countBucketMap provides O(1) access to a specific Bucket with given count. Deleting and adding a Bucket in the Bucket list cost O(1), so both inc() and dec() take strict O(1) time.
    public class AllOne {
        // maintain a doubly linked list of Buckets
        private Bucket head;
        private Bucket tail;
        // for accessing a specific Bucket among the Bucket list in O(1) time
        private Map<Integer, Bucket> countBucketMap;
        // keep track of count of keys
        private Map<String, Integer> keyCountMap;
    
        // each Bucket contains all the keys with the same count
        private class Bucket {
            int count;
            Set<String> keySet;
            Bucket next;
            Bucket pre;
            public Bucket(int cnt) {
                count = cnt;
                keySet = new HashSet<>();
            }
        }
    
        /** Initialize your data structure here. */
        public AllOne() {
            head = new Bucket(Integer.MIN_VALUE);
            tail = new Bucket(Integer.MAX_VALUE);
            head.next = tail;
            tail.pre = head;
            countBucketMap = new HashMap<>();
            keyCountMap = new HashMap<>();
        }
        
        /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
        public void inc(String key) {
            if (keyCountMap.containsKey(key)) {
                changeKey(key, 1);
            } else {
                keyCountMap.put(key, 1);
                if (head.next.count != 1) 
                    addBucketAfter(new Bucket(1), head);
                head.next.keySet.add(key);
                countBucketMap.put(1, head.next);
            }
        }
        
        /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
        public void dec(String key) {
            if (keyCountMap.containsKey(key)) {
                int count = keyCountMap.get(key);
                if (count == 1) {
                    keyCountMap.remove(key);
                    removeKeyFromBucket(countBucketMap.get(count), key);
                } else {
                    changeKey(key, -1);
                }
            }
        }
        
        /** Returns one of the keys with maximal value. */
        public String getMaxKey() {
            return tail.pre == head ? "" : (String) tail.pre.keySet.iterator().next();
        }
        
        /** Returns one of the keys with Minimal value. */
        public String getMinKey() {
            return head.next == tail ? "" : (String) head.next.keySet.iterator().next();        
        }
        
        // helper function to make change on given key according to offset
        private void changeKey(String key, int offset) {
            int count = keyCountMap.get(key);
            keyCountMap.put(key, count + offset);
            Bucket curBucket = countBucketMap.get(count);
            Bucket newBucket;
            if (countBucketMap.containsKey(count + offset)) {
                // target Bucket already exists
                newBucket = countBucketMap.get(count + offset);
            } else {
                // add new Bucket
                newBucket = new Bucket(count + offset);
                countBucketMap.put(count + offset, newBucket);
                addBucketAfter(newBucket, offset == 1 ? curBucket : curBucket.pre);
            }
            newBucket.keySet.add(key);
            removeKeyFromBucket(curBucket, key);
        }
        
        private void removeKeyFromBucket(Bucket bucket, String key) {
            bucket.keySet.remove(key);
            if (bucket.keySet.size() == 0) {
                removeBucketFromList(bucket);
                countBucketMap.remove(bucket.count);
            }
        }
        
        private void removeBucketFromList(Bucket bucket) {
            bucket.pre.next = bucket.next;
            bucket.next.pre = bucket.pre;
            bucket.next = null;
            bucket.pre = null;
        }
        
        // add newBucket after preBucket
        private void addBucketAfter(Bucket newBucket, Bucket preBucket) {
            newBucket.pre = preBucket;
            newBucket.next = preBucket.next;
            preBucket.next.pre = newBucket;
            preBucket.next = newBucket;
        }
    }
    

  • 1
    K

    @AaronLin1992
    Hey Aaron, your solution is clear and clean. However, I get a question, since you are using Integer.MIN_VALUE and Integer.MAX_VALUE as the dummy Head/Tail. What if one of your key actually hit the Integer.MAX_VALUE/MIN_VALUE ? Is it a corner case?


  • 4

    @AaronLin1992

    Nice code! However, when you use iterator().next(), the actual Big O of that call is O(table capacity / N) rather than O(1) like I believe you intended. So by doing this, the code is not truly O(1).

    There is an easy fix, however, by using LinkedHashSet instead of a regular HashSet. In this way, the next() method will truly be O(1).


  • 1
    I
        class ValueNode {
            ValueNode prev, next;
            int val;
            Set<String> strs;
            ValueNode(int v) {
                val = v;
                strs = new LinkedHashSet<>();
            }
            void insertAt(ValueNode node) {
                next = node;
                prev = node.prev;
                next.prev = this;
                prev.next = this;
            }
            void remove(String str) {
                strs.remove(str);
                if (strs.isEmpty()) {
                    prev.next = next;
                    next.prev = prev;
                }
            }
        }
        
        ValueNode valueHead, valueTail; // dummy
        Map<String, ValueNode> keys;
        
        /** Initialize your data structure here. */
        public AllOne() {
            valueHead = new ValueNode(0);
            valueTail = new ValueNode(0);
            valueHead.next = valueTail;
            valueTail.prev = valueHead;
            keys = new HashMap<>();
        }
        
        /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
        public void inc(String key) {
            ValueNode node = keys.getOrDefault(key, valueHead);
            ValueNode vn = node.next;
            if (vn.val != node.val + 1) {
                vn = new ValueNode(node.val + 1);
                vn.insertAt(node.next);
            }
            vn.strs.add(key);
            keys.put(key, vn);
            if (node != valueHead) node.remove(key);
        }
        
        /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
        public void dec(String key) {
            ValueNode node = keys.get(key);
            if (node == null) return;
            if (node.val == 1) {
                keys.remove(key);
                node.remove(key);
                return;
            }
            ValueNode vn = node.prev;
            if (vn.val != node.val - 1) {
                vn = new ValueNode(node.val - 1);
                vn.insertAt(node);
            }
            vn.strs.add(key);
            keys.put(key, vn);
            node.remove(key);
        }
        
        /** Returns one of the keys with maximal value. */
        public String getMaxKey() {
            if (valueTail.prev == valueHead) return "";
            return valueTail.prev.strs.iterator().next();
        }
        
        /** Returns one of the keys with Minimal value. */
        public String getMinKey() {
            if (valueHead.next == valueTail) return "";
            return valueHead.next.strs.iterator().next();
        }
    

  • 0
    O

    @kun5 I think it will be fine with the INT_MIN and INT_MAX because the head and tail are only used as dummy nodes.


  • 0
    L

    Why following code is having a better runtime than original post any idea ?

    Map<String, Integer> value;
    TreeMap<Integer, HashSet<String>> set;
    	
    public AllOne() {
        value = new HashMap<>();
        set = new TreeMap<>();
    }
        
    public void inc(String key) {
            
        if(value.containsKey(key)){
            int val = value.get(key);
        	if(set.containsKey(val)){
        	    HashSet<String> valSet = set.get(val);
        	    valSet.remove(key);
        	    if(valSet.isEmpty())
        		set.remove(val);
        	}
        		
        	value.put(key, val+1);
        	if(set.containsKey(val+1)){
        	    set.get(val+1).add(key);
        	} else {
        	    HashSet<String> valSet = new HashSet<>();
        	    valSet.add(key);
        	    set.put(val+1, valSet);
        	}
        } else {
        	value.put(key, 1);
        	if(set.containsKey(1)){
                set.get(1).add(key);
        	} else {
        	    HashSet<String> valSet = new HashSet<>();
        	    valSet.add(key);
        	    set.put(1, valSet);
        	}
        }    	    	
    }
        
    public void dec(String key) {
        	
        if(value.containsKey(key)){
            int val = value.get(key);
        	if(set.containsKey(val)){
        	    HashSet<String> valSet = set.get(val);
        	    valSet.remove(key);
        	    if(valSet.isEmpty())
        	        set.remove(val);
        	}
        		
        	if(val == 1){
        	    value.remove(key);
        	    return;
        	}
        		
        	value.put(key, val-1);
        	if(set.containsKey(val-1)){
        	    set.get(val-1).add(key);
        	} else {
        	    HashSet<String> valSet = new HashSet<>();
        	    valSet.add(key);
        	    set.put(val-1, valSet);
        	}
        }
    }
        
    public String getMaxKey() {
        if(set.isEmpty())
        	return "";
        	
        HashSet<String> value = set.lastEntry().getValue();
        if(value.isEmpty())
           	return "";
        else 
          	return value.iterator().next();        
    }
        
    public String getMinKey() {
        if(set.isEmpty())
        	return "";
        	
        HashSet<String> value = set.firstEntry().getValue();
        if(value.isEmpty())
           	return "";
        else 
           	return value.iterator().next();
    }
    

  • 1

    @DeusVult Can you provide a reference why you said the time complexity of next() of HashSet() is O(table capacity / N)? Thanks!


  • 2

    @zhugejunwei
    Please referring to the official Java doc of LinkedHashSet.
    "Iteration over a LinkedHashSet requires time proportional to the size of the set, regardless of its capacity. Iteration over a HashSet is likely to be more expensive, requiring time proportional to its capacity. "


  • 0

    @yubad2000 Thanks a lot.


  • 1

    Similar solution implemented using doubled-linked list with LinkedHashSet for storing keys with same counts.
    The key idea of the problem is to build a data structure for "Insertion Sort", which allows insert of delete a key by the current key either +1 or -1. And, each delete, insert. check min or max should be O(1).

    public class AllOne {
        class Node { //Double-Linked List Node
            int count; // the primary key of a Node
            Node left = null, right = null;
            LinkedHashSet<String> keys = new LinkedHashSet<>(); // store the keys of the same count
            Node (int count) {this.count = count;}
            //wrapper functions of Set 
            void add(String key){ keys.add(key); }
            void remove(String key){ keys.remove(key); }
            int size(){ return keys.size(); }  
            // return the first key in the set, which should be O(1) with LinkedHashSet
            String firstKey() { return keys.iterator().next(); }
        }
        
        Node head, tail; //dummy nodes for head and tail of a linked list
        Map<String, Integer> keys = new HashMap<>(); // key counts
        Map<Integer, Node> counts = new HashMap<>(); // index to a Node by count
        /** Initialize your data structure here. */
        public AllOne() {
            head = new Node(0);
            tail = new Node(Integer.MAX_VALUE);
            // the case of no other nodes except two dummies, return "" as min and max keys
            head.add(""); 
            tail.add("");
            head.right = tail;
            tail.left = head;
        }
        // delete a node of the list, (the passing in node can't be the dummy nodes)
        void deleteNode(Node node) {
            node.left.right = node.right;
            node.right.left = node.left;
            node.left = null;
            node.right = null;
        }
        // The passing in node can't be the dummy nodes
        void insertKey(Node node, int num, String key) {
            int count = node.count + num;
            if (count > 0) { //when count == 1, no need to insert the key into a node since it should be removed
                if (counts.containsKey(count) ) { // no need to create new Node if the node with this count exists
                    counts.get(count).add(key);
                } else {
                    // Insert a new node at left size of this node if num = -1
                    // Or, insert a new node at right size of this node if num = 1
                    Node preNode = num > 0 ? node : node.left;
                    Node newNode = new Node(count);
                    newNode.add(key);
                    newNode.right = preNode.right;
                    newNode.left = preNode;
                    preNode.right.left = newNode;
                    preNode.right = newNode;
                    counts.put(count, newNode);
                }
            }
        }
        // remove a key from the list
        void removeKey(int count, String key){
            if (counts.containsKey(count) ) {
                counts.get(count).remove(key);
                // if an empty Node, it should be removed from the list
                if ( counts.get(count).size() == 0 ) {
                    deleteNode(counts.get(count));
                    counts.remove(count);
                }
            }
        }
        /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
        public void inc(String key) {
            if (keys.containsKey(key)){ // eixsting key
                int count = keys.get(key);
                // add key to the Node with primary key of count+1
                insertKey(counts.get(count), 1, key);
                // remove key from the Node with primary key of count
                removeKey(count, key);
                keys.put(key, count+1); // increase the count of this key by 1
            } else { // this is a new key
                keys.put(key, 1);
                insertKey(head, 1, 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 (keys.containsKey(key)){ // eixsting key
                int count = keys.get(key);
                // add key to the Node with primary key of count-1
                insertKey(counts.get(count), -1, key);
                // remove key from the Node with primary key of count
                removeKey(count, key);
                if (count > 1) {
                    keys.put(key, count-1);
                } else {
                    keys.remove(key);
                }
            }
        }
        
        /** Returns one of the keys with maximal value. */
        public String getMaxKey() {
            return tail.left.firstKey(); 
        }
        
        /** Returns one of the keys with Minimal value. */
        public String getMinKey() {
            return head.right.firstKey(); 
        }
    }
    

Log in to reply
 

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