All O(1) Data Structure
Hard · Design · Hash Table · Linked List · Design · Doubly-Linked List
Problem
Design a structure that keeps a count for each string key and can report a key with the highest and the lowest count, with every operation in O(1) average time. Implement the class AllOne:
- AllOne() creates an empty structure.
- inc(key) adds 1 to the count of key, inserting it with count 1 if it is new.
- dec(key) subtracts 1 from the count of key; when the count reaches 0 the key is removed. key is always present when dec is called.
- getMaxKey() returns a key with the largest count, or "" if there are no keys.
- getMinKey() returns a key with the smallest count, or "" if there are no keys.
In general several keys can tie for the largest or smallest count, and any of them is a correct answer. The tests here only call getMaxKey and getMinKey when exactly one key has that count (or there are no keys), so every answer is unique.
Examples
Input: ops = ["AllOne","inc","inc","inc","getMaxKey","getMinKey","dec","dec","getMaxKey"] args = [[],["cat"],["cat"],["dog"],[],[],["cat"],["cat"],[]] Output: [null,null,null,null,"cat","dog",null,null,"dog"]
cat reaches 2 and dog 1. After two decrements cat is gone and dog is the only key.
Input: ops = ["AllOne","getMaxKey","inc","getMinKey"] args = [[],[],["x"],[]] Output: [null,"",null,"x"]
An empty structure reports "". After one inc, the single key is both the minimum and the maximum.
Input: ops = ["AllOne","inc","inc","inc","inc","dec","getMinKey","getMaxKey"] args = [[],["a"],["b"],["b"],["c"],["c"],[],[]] Output: [null,null,null,null,null,null,"a","b"]
c goes to 1 and back to 0, so it disappears: only a (1) and b (2) remain.
Constraints
- 1 <= len(key) <= 10
- key consists of lowercase English letters
- dec is only called on a key that is stored
- At most 5 · 10^4 calls in total
Approaches
- Dictionary of counts, scan for max and min — time O(1) inc/dec, O(k) get, space O(k)
Follow-up
What if getMaxKey had to return the lexicographically smallest of the tied keys? Each bucket would keep its keys in a sorted structure, making updates O(log k) inside a bucket while the bucket list stays O(1).
Related problems
Start free on Cariara · Coding problems · System design studio
