## 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 tail;
private Map<String, Integer> keyValueMap;
private Map<Integer, BucketNode> valueBucketMap;

/** Initialize your data structure here. */
public AllOne() {
tail = new BucketNode(Integer.MAX_VALUE);
keyValueMap  = new HashMap<>();
valueBucketMap = new HashMap<>();
}

/** 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{

}

keyValueMap.put(key, 1);
}
}

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

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