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```c
2#include <stdio.h>
```The solution uses a doubly linked list to store nodes that keep track of key counts, while a hash map points to these nodes for quick updates. Each node's key set is a linked list storing the keys currently having a particular count. When counts are incremented or decremented, keys are moved to adjacent count nodes, ensuring efficient access for getMaxKey and getMinKey.
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```java
2import java.util.*;
3
4class AllOne {
5 private class Bucket {
6 int count;
7 Set<String> keys;
8 Bucket prev, next;
9
10 Bucket(int count) {
11 this.count = count;
12 this.keys = new HashSet<>();
13 }
14 }
15
16 private Map<String, Bucket> keyToBucketMap;
17 private Bucket head, tail;
18
19 public AllOne() {
20 keyToBucketMap = new HashMap<>();
21 head = new Bucket(Integer.MAX_VALUE);
22 tail = new Bucket(Integer.MIN_VALUE);
23 head.next = tail;
24 tail.prev = head;
25 }
26
27 public void inc(String key) {
28 if (!keyToBucketMap.containsKey(key)) {
29 if (tail.prev.count != 1) addBucketAfter(new Bucket(1), tail.prev);
30 tail.prev.keys.add(key);
31 keyToBucketMap.put(key, tail.prev);
32 } else {
33 Bucket bucket = keyToBucketMap.get(key);
34 Bucket next = bucket.next;
35 if (next == null || next.count != bucket.count + 1) next = addBucketAfter(new Bucket(bucket.count + 1), bucket);
36 next.keys.add(key);
37 keyToBucketMap.put(key, next);
38 bucket.keys.remove(key);
39 if (bucket.keys.isEmpty()) removeBucket(bucket);
40 }
41 }
42
43 public void dec(String key) {
44 Bucket bucket = keyToBucketMap.get(key);
45 if (bucket == null) return;
46 if (bucket.count == 1) {
47 keyToBucketMap.remove(key);
48 bucket.keys.remove(key);
49 if (bucket.keys.isEmpty()) removeBucket(bucket);
50 } else {
51 Bucket prev = bucket.prev;
52 if (prev == head || prev.count != bucket.count - 1) prev = addBucketAfter(new Bucket(bucket.count - 1), bucket.prev);
53 prev.keys.add(key);
54 keyToBucketMap.put(key, prev);
55 bucket.keys.remove(key);
56 if (bucket.keys.isEmpty()) removeBucket(bucket);
57 }
58 }
59
60 private Bucket addBucketAfter(Bucket newBucket, Bucket prevBucket) {
61 newBucket.prev = prevBucket;
62 newBucket.next = prevBucket.next;
63 prevBucket.next.prev = newBucket;
64 prevBucket.next = newBucket;
65 return newBucket;
66 }
67
68 private void removeBucket(Bucket bucket) {
69 bucket.prev.next = bucket.next;
70 bucket.next.prev = bucket.prev;
71 }
72
73 public String getMaxKey() {
74 return head.next == tail ? "" : head.next.keys.iterator().next();
75 }
76
77 public String getMinKey() {
78 return tail.prev == head ? "" : tail.prev.keys.iterator().next();
79 }
80}
81```This Java implementation leverages a doubly linked list of buckets, where each bucket holds keys with the same frequency. The frequency is managed by the bucket list, enabling constant-time updates. Each operation (inc, dec, getMaxKey, and getMinKey) requires only local adjustments within a bucket, which makes this structure efficient and fast.