# 432. All Oone Data Structure

## Description

Design a data structure to store the strings' count with the ability to return the strings with minimum and maximum counts.

Implement the AllOne class:

• AllOne() Initializes the object of the data structure.
• inc(String key) Increments the count of the string key by 1. If key does not exist in the data structure, insert it with count 1.
• dec(String key) Decrements the count of the string key by 1. If the count of key is 0 after the decrement, remove it from the data structure. It is guaranteed that key exists in the data structure before the decrement.
• getMaxKey() Returns one of the keys with the maximal count. If no element exists, return an empty string "".
• getMinKey() Returns one of the keys with the minimum count. If no element exists, return an empty string "".

Note that each function must run in O(1) average time complexity.

Example 1:

Input
["AllOne", "inc", "inc", "getMaxKey", "getMinKey", "inc", "getMaxKey", "getMinKey"]
[[], ["hello"], ["hello"], [], [], ["leet"], [], []]
Output
[null, null, null, "hello", "hello", null, "hello", "leet"]

Explanation
AllOne allOne = new AllOne();
allOne.inc("hello");
allOne.inc("hello");
allOne.getMaxKey(); // return "hello"
allOne.getMinKey(); // return "hello"
allOne.inc("leet");
allOne.getMaxKey(); // return "hello"
allOne.getMinKey(); // return "leet"


Constraints:

• 1 <= key.length <= 10
• key consists of lowercase English letters.
• It is guaranteed that for each call to dec, key is existing in the data structure.
• At most 5 * 104 calls will be made to inc, dec, getMaxKey, and getMinKey.

## Solutions

• class AllOne {
Node root = new Node();
Map<String, Node> nodes = new HashMap<>();

public AllOne() {
root.next = root;
root.prev = root;
}

public void inc(String key) {
if (!nodes.containsKey(key)) {
if (root.next == root || root.next.cnt > 1) {
nodes.put(key, root.insert(new Node(key, 1)));
} else {
nodes.put(key, root.next);
}
} else {
Node curr = nodes.get(key);
Node next = curr.next;
if (next == root || next.cnt > curr.cnt + 1) {
nodes.put(key, curr.insert(new Node(key, curr.cnt + 1)));
} else {
nodes.put(key, next);
}
curr.keys.remove(key);
if (curr.keys.isEmpty()) {
curr.remove();
}
}
}

public void dec(String key) {
Node curr = nodes.get(key);
if (curr.cnt == 1) {
nodes.remove(key);
} else {
Node prev = curr.prev;
if (prev == root || prev.cnt < curr.cnt - 1) {
nodes.put(key, prev.insert(new Node(key, curr.cnt - 1)));
} else {
nodes.put(key, prev);
}
}

curr.keys.remove(key);
if (curr.keys.isEmpty()) {
curr.remove();
}
}

public String getMaxKey() {
return root.prev.keys.iterator().next();
}

public String getMinKey() {
return root.next.keys.iterator().next();
}
}

class Node {
Node prev;
Node next;
int cnt;
Set<String> keys = new HashSet<>();

public Node() {
this("", 0);
}

public Node(String key, int cnt) {
this.cnt = cnt;
}

public Node insert(Node node) {
node.prev = this;
node.next = this.next;
node.prev.next = node;
node.next.prev = node;
return node;
}

public void remove() {
this.prev.next = this.next;
this.next.prev = this.prev;
}
}

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

• class Node:
def __init__(self, key='', cnt=0):
self.prev = None
self.next = None
self.cnt = cnt
self.keys = {key}

def insert(self, node):
node.prev = self
node.next = self.next
node.prev.next = node
node.next.prev = node
return node

def remove(self):
self.prev.next = self.next
self.next.prev = self.prev

class AllOne:
def __init__(self):
self.root = Node()
self.root.next = self.root
self.root.prev = self.root
self.nodes = {}

def inc(self, key: str) -> None:
root, nodes = self.root, self.nodes
if key not in nodes:
if root.next == root or root.next.cnt > 1:
nodes[key] = root.insert(Node(key, 1))
else:
nodes[key] = root.next
else:
curr = nodes[key]
next = curr.next
if next == root or next.cnt > curr.cnt + 1:
nodes[key] = curr.insert(Node(key, curr.cnt + 1))
else:
nodes[key] = next
if not curr.keys:
curr.remove()

def dec(self, key: str) -> None:
root, nodes = self.root, self.nodes
curr = nodes[key]
if curr.cnt == 1:
nodes.pop(key)
else:
prev = curr.prev
if prev == root or prev.cnt < curr.cnt - 1:
nodes[key] = prev.insert(Node(key, curr.cnt - 1))
else:
nodes[key] = prev
if not curr.keys:
curr.remove()

def getMaxKey(self) -> str:
return next(iter(self.root.prev.keys))

def getMinKey(self) -> str:
return next(iter(self.root.next.keys))

# Your AllOne object will be instantiated and called as such:
# obj = AllOne()
# obj.inc(key)
# obj.dec(key)
# param_3 = obj.getMaxKey()
# param_4 = obj.getMinKey()

`