[Leetcode] Problem 432 - All O'one Data Structure

Implement a data structure supporting the following operations:

  1. Inc(Key) - Inserts a new key with value 1. Or increments an existing key by 1. Key is guaranteed to be a non-empty string.
  2. Dec(Key) - If Key’s value is 1, remove it from the data structure. Otherwise decrements an existing key by 1. If the key does not exist, this function does nothing. Key is guaranteed to be a non-empty string.
  3. GetMaxKey() - Returns one of the keys with maximal value. If no element exists, return an empty string “”.
  4. GetMinKey() - Returns one of the keys with minimal value. If no element exists, return an empty string “”.

Challenge: Perform all these in O(1) time complexity.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
public class LinkedNode {
private int value;
private Set<String> keys;
private LinkedNode prev;
private LinkedNode next;

public LinkedNode(int value) {
this.value = value;
this.keys = new HashSet<>();
}

public void add(LinkedNode node) {
node.next = this.next;
this.next.prev = node;
this.next = node;
node.prev = this;
}

public void remove(String key) {
this.keys.remove(key);

if (this.keys.isEmpty()) {
this.prev.next = this.next;
this.next.prev = this.prev;
}
}
}

private Map<String, LinkedNode> map;
LinkedNode head;
LinkedNode tail;

public AllOne() {
this.map = new HashMap<>();
this.head = new LinkedNode(-1);
this.tail = new LinkedNode(-1);

head.next = tail;
tail.prev = head;
}

public void inc(String key) {
if (!map.containsKey(key)) {
LinkedNode node = head.next.value == 1 ? head.next : new LinkedNode(1);
node.keys.add(key);

if (head.next.value != 1)
head.add(node);

map.put(key, node);
} else {
LinkedNode node = map.get(key);
LinkedNode newNode = node.value + 1 == node.next.value ? node.next : new LinkedNode(node.value + 1);
newNode.keys.add(key);

if (node.value + 1 != node.next.value)
node.add(newNode);

map.put(key, newNode);
node.remove(key);
}
}

public void dec(String key) {
if (!map.containsKey(key))
return;

LinkedNode node = map.get(key);

if (node.value == 1)
map.remove(key);
else {
LinkedNode newNode = node.prev.value + 1 == node.value ? node.prev : new LinkedNode(node.value - 1);
newNode.keys.add(key);

if (node.prev.value + 1 != node.value)
node.prev.add(newNode);

map.put(key, newNode);
}

node.remove(key);
}

public String getMaxKey() {
return tail.prev == head ? "" : tail.prev.keys.iterator().next();
}

public String getMinKey() {
return head.next == tail ? "" : head.next.keys.iterator().next();
}