Watch 10 video solutions for All O`one Data Structure, a hard level problem involving Hash Table, Linked List, Design. This walkthrough by codestorywithMIK has 11,058 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Design a data structure to store the strings' count with the ability to return the strings with minimum and maximum counts.
Implement the AllOne class:
AllOne() Initializes the object of the data structure.inc(String key) Increments the count of the string key by 1. If key does not exist in the data structure, insert it with count 1.dec(String key) Decrements the count of the string key by 1. If the count of key is 0 after the decrement, remove it from the data structure. It is guaranteed that key exists in the data structure before the decrement.getMaxKey() Returns one of the keys with the maximal count. If no element exists, return an empty string "".getMinKey() Returns one of the keys with the minimum count. If no element exists, return an empty string "".Note that each function must run in O(1) average time complexity.
Example 1:
Input
["AllOne", "inc", "inc", "getMaxKey", "getMinKey", "inc", "getMaxKey", "getMinKey"]
[[], ["hello"], ["hello"], [], [], ["leet"], [], []]
Output
[null, null, null, "hello", "hello", null, "hello", "leet"]
Explanation
AllOne allOne = new AllOne();
allOne.inc("hello");
allOne.inc("hello");
allOne.getMaxKey(); // return "hello"
allOne.getMinKey(); // return "hello"
allOne.inc("leet");
allOne.getMaxKey(); // return "hello"
allOne.getMinKey(); // return "leet"
Constraints:
1 <= key.length <= 10key consists of lowercase English letters.dec, key is existing in the data structure.5 * 104 calls will be made to inc, dec, getMaxKey, and getMinKey.Problem Overview: Design a data structure that stores string keys with integer counts and supports four operations in constant time: inc, dec, getMaxKey, and getMinKey. Each increment or decrement changes a key's frequency, and you must always be able to retrieve any key with the maximum or minimum count in O(1) time.
Approach 1: Doubly Linked List with HashMap (O(1) time, O(n) space)
This approach maintains buckets of keys grouped by frequency using a doubly linked list. Each node in the list represents a specific count and stores a set of keys with that count. A HashMap maps each key to its corresponding bucket node. When you call inc or dec, the key moves to the adjacent bucket representing the updated frequency. If the target bucket does not exist, create it and insert it in the correct position in the list. Because bucket insertion, deletion, and key relocation are all constant-time operations, every API operation runs in O(1) time with O(n) space for storing keys. This design relies heavily on fast lookups from a hash table and constant-time insert/remove operations from a doubly-linked list.
Approach 2: Bucket with Key in Linked HashMap (O(1) time, O(n) space)
This variation also organizes keys by frequency buckets but uses maps to track relationships between counts and keys. A main map stores the current count for each key, while another structure maps each count to a set or ordered collection of keys. Incrementing a key moves it from one bucket to the next higher bucket; decrementing moves it to the previous bucket or removes it if the count reaches zero. Additional variables track the current minimum and maximum counts so getMinKey and getMaxKey return results instantly. The idea is similar to the linked list bucket approach but implemented using maps and sets instead of explicit node pointers. Hash lookups and set updates keep operations at O(1) average time with O(n) total space.
Recommended for interviews: Interviewers usually expect the doubly linked list bucket design. It demonstrates strong understanding of data structure design and how to combine hash maps with linked structures to maintain ordered frequency groups. A naive frequency map alone cannot return min and max keys in constant time. The bucketed linked list solves this by keeping counts sorted implicitly through neighbor pointers.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Doubly Linked List with HashMap | O(1) for all operations | O(n) | Best general solution for interviews and production. Maintains ordered frequency buckets efficiently. |
| Bucket Map with Key Sets | O(1) average | O(n) | Useful in languages with strong map/set support like Python or Java where managing explicit linked nodes is unnecessary. |