All O`one Data Structure

• Use a HashMap<String, Integer> to store the count for each string key.
• inc(key): Retrieve the count of the key, increment it, and update the map. If the key doesn't exist, add it with a count of 1. This is an O(1) average time operation.
• dec(key): Retrieve the count of the key, decrement it, and update the map. If the new count is 0, remove the key from the map. This is an O(1) average time operation.
• getMaxKey() / getMinKey(): Iterate through all the entries in the HashMap. Keep track of the maximum/minimum count seen so far and the corresponding key. Return the key associated with the final maximum/minimum count. This requires a full scan of all unique keys, making it an O(N) operation, where N is the number of unique keys.

The core of this approach is a HashMap<String, Integer> which maps each string key to its frequency count.

For inc(key) and dec(key), we can leverage the HashMap's O(1) average time complexity for get and put operations. To increment, we fetch the current count, add one, and put it back. To decrement, we do the same but subtract one, and if the count reaches zero, we remove the key from the map.

The main drawback appears in getMaxKey() and getMinKey(). Since the counts in the HashMap are not stored in any particular order, the only way to find the minimum or maximum count is to perform a linear scan over all the entries in the map. We iterate through the map, comparing each key's count with the current minimum/maximum found so far, and update it if necessary. This leads to an O(N) time complexity, where N is the number of unique keys stored.

1import java.util.HashMap;2import java.util.Map;3 4class AllOne {5    private Map<String, Integer> counts;6 7    public AllOne() {8        counts = new HashMap<>();9    }10    11    public void inc(String key) {12        counts.put(key, counts.getOrDefault(key, 0) + 1);13    }14    15    public void dec(String key) {16        int count = counts.get(key);17        if (count == 1) {18            counts.remove(key);19        } else {20            counts.put(key, count - 1);21        }22    }23    24    public String getMaxKey() {25        if (counts.isEmpty()) {26            return "";27        }28        String maxKey = "";29        int maxVal = 0;30        for (Map.Entry<String, Integer> entry : counts.entrySet()) {31            if (entry.getValue() > maxVal) {32                maxVal = entry.getValue();33                maxKey = entry.getKey();34            }35        }36        return maxKey;37    }38    39    public String getMinKey() {40        if (counts.isEmpty()) {41            return "";42        }43        String minKey = "";44        int minVal = Integer.MAX_VALUE;45        for (Map.Entry<String, Integer> entry : counts.entrySet()) {46            if (entry.getValue() < minVal) {47                minVal = entry.getValue();48                minKey = entry.getKey();49            }50        }51        return minKey;52    }53}

• Use a HashMap<String, Integer> to map keys to their counts.
• Use a TreeSet to store (count, key) pairs. The TreeSet will automatically keep these pairs sorted based on the count, allowing for fast retrieval of min and max elements.
• inc(key): Get the old count from the HashMap. Remove the old (count, key) pair from the TreeSet. Update the count in the HashMap. Insert the new (count+1, key) pair into the TreeSet. This involves remove and add operations on the TreeSet, which take O(log N) time.
• dec(key): Similar to inc, remove the old pair from the TreeSet, update the count in the HashMap, and insert the new (count-1, key) pair if the new count is greater than 0. This also takes O(log N) time.
• getMaxKey(): Return the key from the last element in the TreeSet (treeSet.last()). This is an O(1) operation.
• getMinKey(): Return the key from the first element in the TreeSet (treeSet.first()). This is an O(1) operation.

To optimize getMaxKey and getMinKey, we need a data structure that keeps track of the order of counts. A balanced binary search tree, such as Java's TreeSet, is a good candidate.

We use two data structures:

1. HashMap<String, Integer> keyToCount: Same as before, for O(1) lookup of a key's count.
2. TreeSet<Pair<Integer, String>> sortedCounts: This set stores pairs of (count, key). It's ordered by count, and then by key lexicographically to handle ties and ensure uniqueness of pairs.

When inc(key) is called, we must perform the following steps:

1. Look up the old count in keyToCount.
2. If the key existed, remove the (oldCount, key) pair from the TreeSet.
3. Increment the count and update keyToCount.
4. Insert the (newCount, key) pair into the TreeSet.

Both removal and insertion in a TreeSet take O(log N) time. The dec operation follows a similar logic. Because the TreeSet is always sorted, getMinKey can be found by looking at the first element (treeSet.first()) and getMaxKey by looking at the last element (treeSet.last()), both in O(1) time.

1import java.util.HashMap;2import java.util.Map;3import java.util.TreeSet;4 5class AllOne {6    // A helper class to store count and key, and define comparison logic.7    private static class Pair implements Comparable<Pair> {8        int count;9        String key;10 11        Pair(int count, String key) {12            this.count = count;13            this.key = key;14        }15 16        @Override17        public int compareTo(Pair other) {18            if (this.count == other.count) {19                return this.key.compareTo(other.key);20            }21            return Integer.compare(this.count, other.count);22        }23    }24 25    private Map<String, Integer> keyToCount;26    private TreeSet<Pair> sortedCounts;27 28    public AllOne() {29        keyToCount = new HashMap<>();30        sortedCounts = new TreeSet<>();31    }32    33    public void inc(String key) {34        int oldCount = keyToCount.getOrDefault(key, 0);35        int newCount = oldCount + 1;36 37        if (oldCount > 0) {38            sortedCounts.remove(new Pair(oldCount, key));39        }40        keyToCount.put(key, newCount);41        sortedCounts.add(new Pair(newCount, key));42    }43    44    public void dec(String key) {45        int oldCount = keyToCount.get(key);46        int newCount = oldCount - 1;47 48        sortedCounts.remove(new Pair(oldCount, key));49        if (newCount == 0) {50            keyToCount.remove(key);51        } else {52            keyToCount.put(key, newCount);53            sortedCounts.add(new Pair(newCount, key));54        }55    }56    57    public String getMaxKey() {58        if (sortedCounts.isEmpty()) {59            return "";60        }61        return sortedCounts.last().key;62    }63    64    public String getMinKey() {65        if (sortedCounts.isEmpty()) {66            return "";67        }68        return sortedCounts.first().key;69    }70}

• Use a HashMap<String, Bucket> to map each key to a Bucket node in a doubly linked list.
• The doubly linked list contains Bucket nodes. Each Bucket represents a specific count and holds a Set<String> of all keys with that count.
• The list of buckets is kept sorted by count. We use head and tail dummy nodes to easily find the min and max buckets (head.next and tail.prev).
• inc(key):
  1. Find the key's current bucket. Let its count be c.
  2. Look for the bucket for count c+1, which should be currentBucket.next.
  3. If currentBucket.next is not for count c+1, create a new bucket for c+1 and insert it.
  4. Move the key from the current bucket's set to the new bucket's set.
  5. Update the key's mapping in the HashMap to point to the new bucket.
  6. If the old bucket becomes empty, remove it from the list.
• dec(key): Works similarly to inc, but moves the key to the bucket for count c-1 (the prev bucket). If the count becomes 0, the key is removed entirely. Empty buckets are cleaned up.
• getMaxKey(): Return any key from the set in the bucket tail.prev.
• getMinKey(): Return any key from the set in the bucket head.next.

This solution is built upon two main data structures:

1. HashMap<String, Bucket> keyToBucketMap: This map provides O(1) access to the Bucket node that a given key currently belongs to.
2. A Doubly Linked List of Buckets: Each Bucket node in the list contains int count and Set<String> keys, where the set holds all keys that have that specific count. The list is maintained in ascending order of count. We use dummy head and tail nodes to simplify list manipulations and provide O(1) access to the minimum and maximum count buckets.

How operations work:

• inc(String key): When a key's count increases from c to c+1, we need to move it from the bucket with count c to the bucket with count c+1. We find the c+1 bucket, which must be immediately after the c bucket in our sorted list. If it doesn't exist, we create it and insert it in the correct position. Then, we move the key from the old bucket's keys set to the new one's and update the keyToBucketMap. If the old bucket becomes empty, we remove it from the list. All these steps—map lookups, set operations, and linked list pointer updates—are O(1) on average.

• dec(String key): This is the reverse of inc. We move the key from bucket c to c-1. If the count drops to 0, we remove the key from keyToBucketMap. Again, we clean up any buckets that become empty.

• getMinKey() / getMaxKey(): Since the list is sorted by count, the bucket with the minimum count is always head.next, and the one with the maximum count is tail.prev. We can retrieve any key from the respective bucket's keys set in O(1) time.

1import java.util.HashMap;2import java.util.HashSet;3import java.util.Map;4import java.util.Set;5 6class AllOne {7    // Bucket node for the doubly linked list8    private static class Bucket {9        int count;10        Set<String> keys;11        Bucket prev;12        Bucket next;13 14        Bucket(int count) {15            this.count = count;16            this.keys = new HashSet<>();17        }18    }19 20    private Map<String, Bucket> keyToBucketMap;21    private Bucket head; // Dummy head22    private Bucket tail; // Dummy tail23 24    public AllOne() {25        keyToBucketMap = new HashMap<>();26        head = new Bucket(0);27        tail = new Bucket(0);28        head.next = tail;29        tail.prev = head;30    }31 32    private void removeBucket(Bucket bucket) {33        bucket.prev.next = bucket.next;34        bucket.next.prev = bucket.prev;35    }36 37    private void insertAfter(Bucket newBucket, Bucket prevBucket) {38        newBucket.prev = prevBucket;39        newBucket.next = prevBucket.next;40        prevBucket.next.prev = newBucket;41        prevBucket.next = newBucket;42    }43 44    public void inc(String key) {45        Bucket currentBucket = keyToBucketMap.getOrDefault(key, head);46        int newCount = currentBucket.count + 1;47 48        Bucket nextBucket = currentBucket.next;49        if (nextBucket.count != newCount) {50            nextBucket = new Bucket(newCount);51            insertAfter(nextBucket, currentBucket);52        }53 54        nextBucket.keys.add(key);55        keyToBucketMap.put(key, nextBucket);56 57        if (currentBucket != head) {58            currentBucket.keys.remove(key);59            if (currentBucket.keys.isEmpty()) {60                removeBucket(currentBucket);61            }62        }63    }64 65    public void dec(String key) {66        Bucket currentBucket = keyToBucketMap.get(key);67        currentBucket.keys.remove(key);68        int newCount = currentBucket.count - 1;69 70        if (newCount > 0) {71            Bucket prevBucket = currentBucket.prev;72            if (prevBucket.count != newCount) {73                prevBucket = new Bucket(newCount);74                insertAfter(prevBucket, currentBucket.prev);75            }76            prevBucket.keys.add(key);77            keyToBucketMap.put(key, prevBucket);78        } else {79            keyToBucketMap.remove(key);80        }81 82        if (currentBucket.keys.isEmpty()) {83            removeBucket(currentBucket);84        }85    }86 87    public String getMaxKey() {88        if (tail.prev == head) {89            return "";90        }91        return tail.prev.keys.iterator().next();92    }93 94    public String getMinKey() {95        if (head.next == tail) {96            return "";97        }98        return head.next.keys.iterator().next();99    }100}