_432.java

package com.fishercoder.solutions;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class _432 {

    public static class Solution1 {

        /**
         * credit: https://discuss.leetcode.com/topic/65634/java-ac-all-strict-o-1-not-average-o-1-easy-to-read/2
         */
        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;
            }
        }
    }
}

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