DSA problem
All O`one Data Structure
Design a data structure to store the strings' count with the ability to return the strings with minimum and maximum counts. Implement inc(key) (insert or increment the count of key by 1), dec(key) (decrement key's count by 1; remove the key entirely when its count drops to zero), getMaxKey() (return any key with the maximal count, or empty string if the store is empty), and getMinKey() (return any key with the minimal count, or empty string if empty).
All four operations must run in O(1). A naive hash-map-of-counts solution makes inc and dec O(1) but getMaxKey and getMinKey become O(n). The trick is to organize keys by count so we can find min/max in constant time.
The optimal design is a doubly linked list of "buckets". Each bucket represents one specific count and contains a set of keys with that count. The list is kept sorted by count: head end has the smallest count, tail end has the largest. A separate hash map sends each key directly to the bucket it currently lives in.
inc(key): locate the key's current bucket (or treat absent keys as count 0). Move the key to the next bucket (count + 1), creating that bucket if it does not exist. If the old bucket becomes empty, unlink it. dec(key): symmetric — move to the previous bucket (count - 1), or delete the key if its count becomes 0. With the linked list of sorted buckets, getMaxKey peeks any key from the tail bucket and getMinKey peeks any key from the head bucket, both in O(1).
Examples
["AllOne","inc","inc","getMaxKey","getMinKey","inc","getMaxKey","getMinKey"]
[[],["hello"],["hello"],[],[],["leet"],[],[]][null,null,null,"hello","hello",null,"hello","leet"]["AllOne","inc","inc","inc","dec","getMaxKey","getMinKey"]
[[],["a"],["b"],["b"],["b"],[],[]][null,null,null,null,null,"b","a"]["AllOne","getMaxKey","getMinKey"]
[[],[],[]][null,"",""]Constraints
- 1 <= key.length <= 10
- key consists of lowercase English letters.
- It is guaranteed that for each call to dec, the key exists in the data structure.
- At most 5 * 10^4 calls will be made to inc, dec, getMaxKey, and getMinKey.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.