432. All O`one Data Structure

Implement a data structure supporting the following operations:

1. Inc(Key) - Inserts a new keywith 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.

Thoughts:

1. Inc, Dec (key) O(1) -> Map(key, val)

2. getMaxKey(), getMinKey() O(1): doubly LinkedList with head and tail bucketNode (each bucket contains key with the same count value)

Code

class AllOne {

    private class BucketNode{
        int val;
        BucketNode count;
        BucketNode pre;
        BucketNode next;
        Set<String> keySet;
        private BucketNode(int val){
            this.val = val;
            keySet = new HashSet<>();
        }

    }

    private BucketNode head;
    private BucketNode tail;
    private Map<String, Integer> keyValueMap;
    private Map<Integer, BucketNode> valueBucketMap;

    /** Initialize your data structure here. */
    public AllOne() {
         head = new BucketNode(Integer.MIN_VALUE);
         tail = new BucketNode(Integer.MAX_VALUE);
         keyValueMap  = new HashMap<>();
         valueBucketMap = new HashMap<>();
         // link head and tail
         head.next = tail;
         tail.pre = 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)){
            changeValue(key, 1);            
        }
        else{

            if(head.next.val != 1){
                addBucketAfter(new BucketNode(1),head);
            }

            head.next.keySet.add(key);

            // add the mapping
            keyValueMap.put(key, 1);
            valueBucketMap.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(keyValueMap.containsKey(key)){
            if(keyValueMap.get(key) == 1){
                // remove key from KV map
                keyValueMap.remove(key);
                // remove key from Bucket
                removeKeyfromBucket(valueBucketMap.get(1), key);
            }
            else{
                changeValue(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();
    }

    private void changeValue(String key, int offset){
        int curVal = keyValueMap.get(key);
        BucketNode curBucket = valueBucketMap.get(curVal);
        BucketNode newBucket;
        if(valueBucketMap.containsKey(curVal + offset)){
            newBucket = valueBucketMap.get(curVal + offset);
        }
        else{
            newBucket = new BucketNode(curVal + offset);
            addBucketAfter(newBucket, offset == 1 ?curBucket: curBucket.pre);
            valueBucketMap.put(curVal + offset, newBucket);
        }

        // remove the key from curBucket
        removeKeyfromBucket(curBucket, key);

        // add the key to newBucket
        newBucket.keySet.add(key);
        // update the record
        keyValueMap.put(key, curVal + offset);

    }

    private void addBucketAfter(BucketNode newBucket, BucketNode pre){
        newBucket.pre = pre;
        newBucket.next = pre.next;
        pre.next.pre = newBucket;
        pre.next = newBucket;

    }

    private void removeKeyfromBucket(BucketNode bucket, String key){
        // remove key from bucket
        bucket.keySet.remove(key);
        if(bucket.keySet.size() == 0){
            removeBucketfromBucketList(bucket);
            valueBucketMap.remove(bucket.val);
        }
    }

    private void removeBucketfromBucketList(BucketNode bucket){
        bucket.pre.next = bucket.next;
        bucket.next.pre = bucket.pre;
        bucket.pre = null;
        bucket.next = null;
    }
}

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