Sponsored
Sponsored
This approach involves using a hash map to store the frequency of each key and a doubly linked list (DLL) to keep track of the keys at each frequency level. Each node in the DLL represents a unique frequency and holds a set of keys that have the same frequency. This data structure allows us to efficiently update, delete, and access keys while keeping track of the frequencies.
Time Complexity: Each of the operations—inc, dec, getMaxKey, and getMinKey—takes O(1) on average.
Space Complexity: O(K) for storing the keys and their corresponding nodes, where K is the number of unique keys.
1```cpp
2#include <unordered_map>
3#include <unordered_set>
4#include <list>
5#include <string>
6using namespace std;
7
8class AllOne {
9public:
10 AllOne() {
11 bucketList.emplace_back(0);
12 head = bucketList.begin();
13 }
14 void inc(string key) {
15 if (!keyCountMap.count(key)) {
16 keyCountMap[key] = head;
17 head->keys.insert(key);
18 moveForward(key);
19 } else {
20 moveForward(key);
21 }
22 }
23 void dec(string key) {
24 moveBackward(key);
25 }
26 string getMaxKey() {
27 if (head->next == bucketList.end()) return "";
28 return head->next->keys.empty() ? "" : *(head->next->keys.begin());
29 }
30 string getMinKey() {
31 if (head->keys.empty()) return "";
32 return *(head->keys.begin());
33 }
34private:
35 struct Bucket {
36 int count;
37 unordered_set<string> keys;
38 Bucket(int c) : count(c) {}
39 };
40 list<Bucket> bucketList;
41 unordered_map<string, list<Bucket>::iterator> keyCountMap;
42 list<Bucket>::iterator head;
43
44 void moveForward(string key) {
45 auto it = keyCountMap[key];
46 auto itNext = it;
47 ++itNext;
48 if (itNext == bucketList.end() || itNext->count != it->count + 1) {
49 auto insertIt = bucketList.insert(itNext, Bucket(it->count + 1));
50 itNext = insertIt;
51 }
52 keyCountMap[key] = itNext;
53 itNext->keys.insert(key);
54 it->keys.erase(key);
55 if (it->keys.empty() && it != head) {
56 bucketList.erase(it);
57 }
58 }
59
60 void moveBackward(string key) {
61 auto it = keyCountMap[key];
62 if (it != head) {
63 auto itPrev = it;
64 --itPrev;
65 if (itPrev->count != it->count - 1) {
66 auto insertIt = bucketList.insert(it, Bucket(it->count - 1));
67 itPrev = insertIt;
68 }
69 keyCountMap[key] = itPrev;
70 itPrev->keys.insert(key);
71 } else {
72 keyCountMap.erase(key);
73 }
74 it->keys.erase(key);
75 if (it->keys.empty()) {
76 bucketList.erase(it);
77 }
78 }
79};
80```This solution uses an unordered map to quickly access the element's frequency node in the key-count map. The solution maintains a list of buckets, where each bucket stores the keys with the same frequency. Increment or decrement operations effectively modify an element's position in this list with minimal searching, preserving O(1) complexity.
This approach utilizes a linked hash map where the keys are linked, ensuring a constant-time access. Frequencies are stored in hash maps that maintain the order of the elements. Keys are moved forward and backward among buckets when incrementing and decrementing, respectively. This combination allows the solution to be optimal with respect to speed and space.
Time Complexity: Each operation incurs only O(1) time on average due to the hash map use.
Space Complexity: O(K) in terms of storage for keys and nodes, where K is the number of unique keys.
1```python
2class Bucket:
3
```In this Python implementation, a hash map associates keys with their buckets and enables constant-time access to any key's current count. The buckets themselves form a doubly linked list with nodes that represent possible key counts. The operations maintain constant-time complexity by operating primarily within these local bucket objects.