# 432. All O\`one Data Structure



```
T: O(n + clogc)
S: O(n + c)
```

````java
```java
class AllOne {

    Map<String, Integer> counterMap;
    TreeMap<Integer, Set<String>> sortedCountMap;

    public AllOne() {
        this.counterMap = new HashMap<>();
        this.sortedCountMap = new TreeMap<>();
    }
    
    public void inc(String key) {
        if (counterMap.containsKey(key)) {
            int oldCount = counterMap.get(key);
            removeSortedCountMap(oldCount, key);
        }

        int newCount = counterMap.getOrDefault(key, 0) + 1; // hello, 2
        counterMap.put(key, newCount);

        addSortedCountMap(newCount, key); // 2, [hello]
    }
    
    public void dec(String key) {
        int oldCount = counterMap.get(key);
        removeSortedCountMap(oldCount, key);

        int newCount = oldCount - 1;
        counterMap.put(key, newCount);
        
        if (newCount != 0) {
            addSortedCountMap(newCount, key);
        } else {
            counterMap.remove(key);
        }

    }

    private void removeSortedCountMap(int oldCount, String key) {
        Set<String> keys = sortedCountMap.get(oldCount);
        keys.remove(key);

        if (keys.isEmpty()) {
            sortedCountMap.remove(oldCount);
        }
    }

    private void addSortedCountMap(int newCount, String key) {
        sortedCountMap.putIfAbsent(newCount, new HashSet<>());
        sortedCountMap.get(newCount).add(key);
    }
    
    public String getMaxKey() {
        String result = "";
        if (sortedCountMap.size() == 0) {
            return "";
        }

        Integer lastKey = sortedCountMap.lastKey();
        if (lastKey == null) {
            return "";
        }
        Set<String> keys = sortedCountMap.get(lastKey);
        if (keys.isEmpty()) {
            return "";
        }
        for (String key : keys) {
            result = key;
            break;
        }
        return result;
    }
    
    public String getMinKey() {
        String result = "";
        if (sortedCountMap.size() == 0) {
            return "";
        }

        Integer firstKey = sortedCountMap.firstKey();
        if (firstKey == null) {
            return "";
        }
        Set<String> keys = sortedCountMap.get(firstKey);
        if (keys.isEmpty()) {
            return "";
        }
        for (String key : keys) {
            result = key;
            break;
        }
        return result;
    }
}

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

T: O(n + clogc)
S: O(n + c)

key, count

when update count, find old count first, remove from set

update new count and set
if count is 0, no need update

add to another one
count, Set<key>

getLastKey()
getFirstKey()


a 1
b 2

 */
```
````
