Design a data structure that supports inc(key), dec(key), getMaxKey(), getMinKey() all in O(1).
inc("a"), inc("b"), inc("b"), inc("c"), inc("c"), inc("c"), getMaxKey()→"c", getMinKey()→"a"
Use a doubly linked list of buckets sorted by count. Each bucket has a set of keys with that count. HashMap maps key→bucket. inc/dec move key between adjacent buckets.
- DLL of Bucket(count, Set). Map keyToBucket.
- inc(key): if bucket+1 exists after current, add key there; else create new bucket. Remove from old bucket.
- dec(key): similarly move to bucket-1.
- getMaxKey: return any key from tail.prev bucket.
- getMinKey: return any key from head.next bucket.
import java.util.*;
class AllOne {
private static class Bucket {
int count; Set<String> keys = new LinkedHashSet<>();
Bucket prev, next;
Bucket(int c) { count = c; }
}
Bucket head = new Bucket(0), tail = new Bucket(Integer.MAX_VALUE);
Map<String, Bucket> map = new HashMap<>();
public AllOne() { head.next=tail; tail.prev=head; }
private void insertAfter(Bucket node, Bucket newNode) {
newNode.prev=node; newNode.next=node.next;
node.next.prev=newNode; node.next=newNode;
}
private void remove(Bucket node) {
node.prev.next=node.next; node.next.prev=node.prev;
}
public void inc(String key) {
if (!map.containsKey(key)) {
if (head.next.count != 1) insertAfter(head, new Bucket(1));
head.next.keys.add(key); map.put(key, head.next);
} else {
Bucket cur = map.get(key), next = cur.next;
if (next == tail || next.count != cur.count+1) insertAfter(cur, new Bucket(cur.count+1));
cur.next.keys.add(key); map.put(key, cur.next);
cur.keys.remove(key); if (cur.keys.isEmpty()) remove(cur);
}
}
public void dec(String key) {
Bucket cur = map.get(key), prev = cur.prev;
cur.keys.remove(key);
if (cur.count-1 > 0) {
if (prev == head || prev.count != cur.count-1) insertAfter(prev, new Bucket(cur.count-1));
cur.prev.keys.add(key); map.put(key, cur.prev);
} else { map.remove(key); }
if (cur.keys.isEmpty()) remove(cur);
}
public String getMaxKey() { return tail.prev == head ? "" : tail.prev.keys.iterator().next(); }
public String getMinKey() { return head.next == tail ? "" : head.next.keys.iterator().next(); }
}
- Time Complexity: All operations O(1)
- Space Complexity: O(N)