Leetcode 432. All O`one Data Structure
Problem Explanation
Given four different functions with various tasks to perform:
-
Inc(Key)
: This function will insert a new key with value 1. If the key already exists, it increments the current key value by 1. The key is guaranteed to be a non-empty string. -
Dec(Key)
: This function checks if the key's value is 1, then removes it from the data structure. If key value is greater than 1, then it decrements the key value by 1. If the specified key does not exist in the data structure, nothing would be done. The key is also a non-empty string. -
GetMaxKey()
: This function retrieves one of the keys which has the maximum value. If there is no key available in the data structure, then it returns an empty string""
. -
GetMinKey()
: Similar toGetMaxKey()
, but it returns one of the keys with the minimum value. If there are no keys in the data structure, it returns an empty string""
.
The challenge here is to implement these functions in a way they execute in O(1) time complexity, which means regardless of the number of elements in the data structure, all operations should be done in constant time.
Approach Explanation
The solution uses a combination of a doubly linked list and a hashmap. The list node keeps the count of the keys and each node is linked with the next higher and lower count. Each node also holds a hashmap of keys which have the same count, for constant time access.
1
2
3Doubly LinkedList Node:
4 - count
5 - keys with count = count
6 * insert key in constant time
7 * delete key in constant time
8 * get any key in constant time
9 - prev node : previous count
10 - next node : next count
The hashmap keyToIterator
stores the keys and a pointer to its associated Node in the linked list.
On inc(key)
operation, the solution does the following:
- if the key doesn't exist, a new Node is created and appended at the front or inserted after the node with count 1.
- if the key does exist, the key is moved to the next Node. If the next Node has a different count, a new Node is created. Once the key is moved, if the present Node doesn't have any keys, the Node is removed.
On dec(key)
operation:
- if the key doesn't exist, the function does nothing.
- if the key exists and the count is more than 1, the key is moved to the previous Node. If the previous Node has different count, again a new Node is created. Once the key is moved, if the present Node doesn't contain any keys, the Node is removed.
- if the key exists and the count is 1, the key is simply removed. If after removal, the Node doesn't contain any keys, the Node is removed from the linked list.
getMaxKey()
and getMinKey()
operations just return the any key from the respective Node in constant time.
Example Walk-through
Let's consider we have following keys and associated counts:
1 2 3keys = ["A", "B", "C", "D", "E"] 4counts = [3, 2, 4, 1, 3]
Which means "A" is present 3 times, "B" is present 2 times and so on.
Our linked list would look like this:
1 2 31 - ["D"] 42 - ["B"] 53 - ["A", "E"] 64 - ["C"]
When we call inc("A")
, the count of "A" becomes 4 and our linked list becomes:
1 2 31 - ["D"] 42 - ["B"] 53 - ["E"] 64 - ["A", "C"]
When we call dec("C")
, the count of "C" becomes 3 and our linked list becomes:
1 2 31 - ["D"] 42 - ["B"] 53 - ["E", "C"] 64 - ["A"]
When we call getMaxKey()
, it returns "A", and when we call getMinKey()
, it returns "D".# Solutions
Solution in Python
1
2python
3from collections import defaultdict
4from collections import OrderedDict
5
6class Node:
7 def __init__(self, count=0):
8 self.keys = OrderedDict()
9 self.count = count
10
11class AllOne:
12 def __init__(self):
13 self.d = {}
14 self.dll = Node(0)
15 self.dll.next = self.dll.prev = self.dll
16
17 def inc(self, key: str) -> None:
18 if key in self.d:
19 self.removeKey(self.d[key], key)
20 else:
21 self.d[key] = self.dll.next
22 self.addNode(self.d[key].prev, Node(self.d[key].count+1), key)
23
24 def dec(self, key: str) -> None:
25 if key in self.d:
26 if self.d[key].count > 1:
27 if self.d[key].next.count == self.d[key].count-1:
28 nxt = self.d[key].next
29 else:
30 nxt = self.addNode(self.d[key], Node(self.d[key].count-1))
31 self.removeKey(self.d[key], key)
32 nxt.keys[key] = None
33 self.d[key] = nxt
34 else:
35 self.removeKey(self.d[key], key)
36
37 def getMaxKey(self) -> str:
38 if self.dll.prev.count > 0:
39 return next(iter(self.dll.prev.keys))
40 return ''
41
42 def getMinKey(self) -> str:
43 if self.dll.next.count > 0:
44 return next(iter(self.dll.next.keys))
45 return ''
46
47 def addNode(self, prevNode, node: Node, key: str=None) -> Node:
48 nxt = prevNode.next
49 prevNode.next = nxt.prev = node
50 node.next = nxt
51 node.prev = prevNode
52 if key:
53 node.keys[key] = None
54 self.d[key] = node
55 return node
56
57 def removeKey(self, node: Node, key: str) -> None:
58 del node.keys[key]
59 if len(node.keys) == 0:
60 node.prev.next = node.next
61 node.next.prev = node.prev
Solution in Java
1
2java
3import java.util.HashMap;
4
5class Node {
6 int count;
7 HashMap<String, Node> keys = new HashMap<>();
8 Node prev, next;
9
10 Node(int count) {
11 this.count = count;
12 }
13}
14
15public class AllOne {
16 Node head, tail;
17 HashMap<String, Node> keyMap = new HashMap<>();
18
19 public AllOne() {
20 head = new Node(0);
21 tail = new Node(0);
22 head.next = tail;
23 tail.prev = head;
24 }
25
26 public void inc(String key) {
27 if (!keyMap.containsKey(key))
28 insertAfter(head, key);
29 else
30 insertAfter(keyMap.get(key), key);
31 }
32
33 public void dec(String key) {
34 if (keyMap.containsKey(key)) {
35 Node node = keyMap.get(key);
36 if (node.count > 1) {
37 if (node.prev.count != node.count - 1)
38 addNode(node.prev, node.count - 1);
39 node.prev.keys.put(key, node.prev);
40 }
41 node.keys.remove(key);
42 if (node.keys.isEmpty())
43 remove(node);
44 }
45 }
46
47 public String getMaxKey() {
48 return tail.prev == head ? "" : tail.prev.keys.keySet().iterator().next();
49 }
50
51 public String getMinKey() {
52 return head.next == tail ? "" : head.next.keys.keySet().iterator().next();
53 }
54
55 private void insertAfter(Node node, String key) {
56 if (node.next.count != node.count + 1)
57 addNode(node, node.count + 1);
58 node.next.keys.put(key, node.next);
59 if (!node.keys.isEmpty())
60 node.keys.remove(key);
61 if (node.keys.isEmpty() && node.count > 0)
62 remove(node);
63 }
64
65 private void addNode(Node prevNode, int count) {
66 Node node = new Node(count);
67 node.prev = prevNode;
68 node.next = prevNode.next;
69 node.prev.next = node;
70 node.next.prev = node;
71 }
72
73 private void remove(Node node) {
74 node.prev.next = node.next;
75 node.next.prev = node.prev;
76 }
77}
These solutions utilize a frequently used Data Structure concept - using an Hash Map combined with a Doubly Linked List. This concept can be used to solve similar problems as well.
This allows us to perform each operation like searching, getting maximum and minimum value in O(1)
time.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.