All O`one Data Structure LeetCode solution in Java

1
// Intuitions get from the top answer by @AaronLin1992
2
class AllOne {
3
  // Thoughts
4
  // inc() and dec() can be done with a Simple Map, but how do we getMaxKey() and getMinKey() in
5
  // O(1)?
6
  // in order to get max and/or min on the fly, we need to maintain some kind of ordering so that we
7
  // can always access max and min
8
  // to maintain some kind of ordering, the first thing we think about is arrays/lists, however,
9
  // arrays/lists when insert and delete in the middle, it is O(N) operation
10
  // so instead, a linked list might work
11
  // as a result, we considering using Map(s) and LinkedList for our supporting data structures,
12
  // details below
13

14
  private Map<String, Bucket> stringToBucket; // maps a string to bucket
15
  private Map<Integer, Bucket>
16
      countToBucket; // maps string count to bucket, note that because when we design this we can
17
  // have multiple strings in a bucket, that makes it convenient so that for each
18
  // count, we only need 1 bucket, thus the map data structure
19
  private BucketList bucketList;
20

21
  // first, we need to create a class for the LinkedList elements
22
  class Bucket {
23
    private Bucket prev;
24
    private Bucket next;
25

26
    private int count; // recording the count of instances
27
    private Set<String>
28
        keys; // note that we are using Set of Strings. The reason is because multiple Strings can
29

30
    // have the same count and we want to put them in one bucket. This makes the problem
31
    // easier to solve instead of putting them into different buckets.
32

33
    Bucket() {
34
      this.keys = new HashSet<>();
35
    }
36

37
    Bucket(String key) {
38
      this();
39
      this.count = 1;
40
      this.keys.add(key);
41
    }
42
  }
43

44
  // second, we need to create a linked list data structure of buckets
45
  class BucketList {
46
    private Bucket dummyHead; // the fake head before the real head //useful for getMinKey()
47
    private Bucket dummyTail; // the fake tail before the real tail //useful for getMaxKey()
48

49
    public BucketList() {
50
      dummyHead = new Bucket();
51
      dummyTail = new Bucket();
52
      dummyHead.next = dummyTail;
53
      dummyTail.prev = dummyHead;
54
    }
55

56
    public Bucket createNewBucket(String key) {
57
      Bucket bucket = new Bucket(key);
58

59
      Bucket nextBucket = dummyHead.next;
60
      dummyHead.next = bucket;
61
      bucket.prev = dummyHead;
62
      nextBucket.prev = bucket;
63
      bucket.next = nextBucket;
64

65
      return bucket;
66
    }
67

68
    public Bucket createBucketToTheRight(Bucket fromBucket, String key, int count) {
69
      // initialize
70
      Bucket toBucket = new Bucket(key);
71
      toBucket.count = count;
72

73
      Bucket nextBucket = fromBucket.next;
74
      fromBucket.next = toBucket;
75
      toBucket.prev = fromBucket;
76
      nextBucket.prev = toBucket;
77
      toBucket.next = nextBucket;
78

79
      return toBucket;
80
    }
81

82
    public Bucket createBucketToTheLeft(Bucket fromBucket, String key, int count) {
83
      // initialize
84
      Bucket toBucket = new Bucket(key);
85
      toBucket.count = count;
86

87
      Bucket prevBucket = fromBucket.prev;
88
      prevBucket.next = toBucket;
89
      toBucket.prev = prevBucket;
90
      fromBucket.prev = toBucket;
91
      toBucket.next = fromBucket;
92

93
      return toBucket;
94
    }
95

96
    public boolean clean(Bucket oldBucket) { // clean bucket if bucket does not have any keys
97
      if (!oldBucket.keys.isEmpty()) {
98
        return false;
99
      }
100

101
      removeBucket(oldBucket);
102

103
      return true;
104
    }
105

106
    public void removeBucket(Bucket bucket) {
107
      Bucket prevBucket = bucket.prev;
108
      Bucket nextBucket = bucket.next;
109

110
      prevBucket.next = nextBucket;
111
      nextBucket.prev = prevBucket;
112
    }
113
  }
114

115
  public AllOne() {
116
    this.stringToBucket = new HashMap<>();
117
    this.countToBucket = new HashMap<>();
118
    this.bucketList = new BucketList();
119
  }
120

121
  public void inc(String key) {
122
    // first check if the string already present
123
    if (!stringToBucket.containsKey(key)) { // if not present
124
      Bucket bucket = null;
125

126
      // check if there is count of 1 bucket already
127
      if (!countToBucket.containsKey(1)) { // if does not contain count of 1
128
        // we need to create a new bucket for count of 1 and add to the head (the minimum). Because
129
        // count 1 should be the minimum exists in the bucket list
130
        bucket = bucketList.createNewBucket(key);
131
      } else { // if contains count of 1
132
        // then we just need to add the key to the bucket
133
        bucket = countToBucket.get(1);
134
        bucket.keys.add(key);
135
      }
136

137
      // don't forget to update the maps
138
      stringToBucket.put(key, bucket);
139
      countToBucket.put(1, bucket);
140
    } else { // if the key alreay present
141
      // first of all we need to get the current count for the key
142
      Bucket oldBucket = stringToBucket.get(key);
143
      Bucket newBucket = null;
144

145
      int count = oldBucket.count;
146
      count++; // increment 1
147
      // don't forget that we need to remove the key from existing bucket
148
      oldBucket.keys.remove(key);
149

150
      // now let's add the key with new count
151
      if (countToBucket.containsKey(count)) { // if there is already a bucket for this count
152
        // then just add to the set of keys
153
        newBucket = countToBucket.get(count);
154
        newBucket.keys.add(key);
155
      } else { // if there is no bucket for this count, create a new bucket, but where to place it?
156
        // Ans: to the right of the old bucket
157
        newBucket = bucketList.createBucketToTheRight(oldBucket, key, count);
158
      }
159

160
      // special scenario: if old bucket don't have any keys after removing the last key, then we
161
      // need to remove the entire old bucket from the bucket list
162
      if (bucketList.clean(oldBucket)) {
163
        countToBucket.remove(oldBucket.count); // remove from map because the old bucket was removed
164
      }
165

166
      // don't forget to update the maps
167
      stringToBucket.put(key, newBucket);
168
      countToBucket.putIfAbsent(count, newBucket);
169
    }
170
  }
171

172
  public void dec(String key) {
173
    // since it is given that "It is guaranteed that key exists in the data structure before the
174
    // decrement." we don't do additional validation for key exists here
175
    Bucket oldBucket = stringToBucket.get(key);
176
    Bucket newBucket = null;
177

178
    int count = oldBucket.count;
179
    count--; // decrement
180
    oldBucket.keys.remove(key);
181

182
    // special scenario - when count == 0
183
    if (count == 0) {
184
      stringToBucket.remove(key);
185
    } else {
186
      // now let's find a new bucket for the decremented count
187
      if (countToBucket.containsKey(count)) { // if there is already a bucket for the count
188
        newBucket = countToBucket.get(count);
189
        newBucket.keys.add(key);
190
      } else { // if there is no bucket for the count, then following similar logic as before, we
191
        // need to add a bucket to the left of the existing bucket
192
        newBucket = bucketList.createBucketToTheLeft(oldBucket, key, count);
193
      }
194

195
      // don't forget to update the maps
196
      stringToBucket.put(key, newBucket);
197
      countToBucket.putIfAbsent(count, newBucket);
198
    }
199

200
    // special scenario: if old bucket don't have any keys after removing the last key, then we need
201
    // to remove the entire old bucket from the bucket list
202
    if (bucketList.clean(oldBucket)) {
203
      countToBucket.remove(oldBucket.count); // remove from map because the old bucket was removed
204
    }
205
  }
206

207
  public String getMaxKey() {
208
    Set<String> maxSet = bucketList.dummyTail.prev.keys;
209

210
    return maxSet.isEmpty()
211
        ? ""
212
        : maxSet
213
            .iterator()
214
            .next(); // if maxSet is empty, that means the bucketList don't have actual buckets
215
  }
216

217
  public String getMinKey() {
218
    Set<String> minSet = bucketList.dummyHead.next.keys;
219

220
    return minSet.isEmpty()
221
        ? ""
222
        : minSet
223
            .iterator()
224
            .next(); // if minSet is empty, that means the bucketList don't have actual buckets
225
  }
226
}
227

228
/**
229
 * Your AllOne object will be instantiated and called as such: AllOne obj = new AllOne();
230
 * obj.inc(key); obj.dec(key); String param_3 = obj.getMaxKey(); String param_4 = obj.getMinKey();
231
 */