Formatted question description: https://leetcode.ca/all/432.html

432. All Oone Data Structure

Hard

Description

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.

Solution

To do all the operations in O(1) time complexity, create a class DoublyLinkedNode, which contains a value, a set of all keys that have the value, the previous node and the next node. In class AllOne, maintain the head and the tail of the doubly-linked list, where the node with the minimum value is after the head and the node with the maximum value is before the tail. Also maintain two maps. The first map stores each key and the corresponding value. The second map stores each value and the node of the value.

For the constructor, initialize the two maps and initialize the head node and the tail node to have value -1 and head.next = tail and tail.prev = head.

For method inc, there are two cases. If the key already exists, update the value and update the maps the corresponding nodes. Otherwise, create a new node with value 1 and the current key.

For method dec, only consider the case when the key exists. The case is similar to inc, but the case when the value is decreased to 0 needs to be considered individually.

For method getMaxKey, obtain the node just before the tail, and return any key in the node’s set. If the list is empty, return an empty string.

For method getMinKey, obtain the node just after the head, and return any key in the node’s set. If the list is empty, return an empty string.

• class AllOne {
Map<String, Integer> keyValueMap;

/** Initialize your data structure here. */
public AllOne() {
keyValueMap = new HashMap<String, Integer>();
}

/** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
public void inc(String key) {
if (keyValueMap.containsKey(key)) {
int value = keyValueMap.get(key);
int newValue = value + 1;
keyValueMap.put(key, newValue);
DoublyLinkedNode prev = node.prev, next = node.next;
node.keySet.remove(key);
if (node.keySet.isEmpty()) {
prev.next = next;
next.prev = prev;
valueNodeMap.remove(value);
}
if (next.value == node.value + 1)
else {
valueNodeMap.put(newValue, newNode);
prev = next.prev;
prev.next = newNode;
next.prev = newNode;
newNode.prev = prev;
newNode.next = next;
}
} else {
keyValueMap.put(key, 1);
if (node == null) {
valueNodeMap.put(1, node);
prevNext.prev = node;
node.next = prevNext;
} else
}
}

/** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
public void dec(String key) {
if (keyValueMap.containsKey(key)) {
int value = keyValueMap.get(key);
int newValue = value - 1;
if (newValue > 0)
keyValueMap.put(key, newValue);
else
keyValueMap.remove(key);
DoublyLinkedNode prev = node.prev, next = node.next;
node.keySet.remove(key);
if (node.keySet.isEmpty()) {
prev.next = next;
next.prev = prev;
valueNodeMap.remove(value);
}
if (prev.value == node.value - 1)
else if (newValue > 0) {
valueNodeMap.put(newValue, newNode);
next = prev.next;
prev.next = newNode;
next.prev = newNode;
newNode.prev = prev;
newNode.next = next;
}
}
}

/** Returns one of the keys with maximal value. */
public String getMaxKey() {
return "";
else
return tail.prev.keySet.iterator().next();
}

/** Returns one of the keys with Minimal value. */
public String getMinKey() {
return "";
else
}
}

int value;
Set<String> keySet;

this(0);
}

this.value = value;
this.keySet = new HashSet<String>();
}

public DoublyLinkedNode(int value, String key) {
this.value = value;
this.keySet = new HashSet<String>();
}
}

/**
* 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 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()

############

class List(object):
@staticmethod
def delete(elem):
elem.prev.next = elem.next
elem.next.prev = elem.prev
elem.next = elem.prev = None
return elem

@staticmethod
def move(elem, newPrev, newNext):
elem.prev = newPrev
elem.next = newNext
newPrev.next = elem
newNext.prev = elem

@staticmethod

@staticmethod

@staticmethod

@staticmethod

class Node(object):
def __init__(self, val):
self.val = val
self.prev = None
self.next = None
self.keys = set()

self.keys |= {key}

def remove(self, key):
self.keys -= {key}

def isEmpty(self):
return len(self.keys) == 0

def peepKey(self):
for k in self.keys:
return k
return ""

class AllOne(object):

def __init__(self):
"""
"""
self.d = {}

def inc(self, key):
"""
Inserts a new key <Key> with value 1. Or increments an existing key by 1.
:type key: str
:rtype: void
"""
if key not in self.d:
else:
newNode = Node(1)
self.d[key] = newNode
else:
node = self.d[key]
newNode = None
if node.next.val != node.val + 1:
newNode = Node(node.val + 1)
List.insertAfter(node, newNode)
else:
newNode = node.next

node.remove(key)
if node.isEmpty():
List.delete(node)
del self.d[key]
self.d[key] = newNode

def dec(self, key):
"""
Decrements an existing key by 1. If Key's value is 1, remove it from the data structure.
:type key: str
:rtype: void
"""
if key not in self.d:
return
node = self.d[key]
if node.val == 1:
node.remove(key)
if node.isEmpty():
List.delete(node)
del self.d[key]
else:
newNode = None
if node.prev.val != node.val - 1:
newNode = Node(node.val - 1)
List.insertAfter(node.prev, newNode)
else:
newNode = node.prev
node.remove(key)
if node.isEmpty():
List.delete(node)
del self.d[key]
self.d[key] = newNode

def getMaxKey(self):
"""
Returns one of the keys with maximal value.
:rtype: str
"""

def getMinKey(self):
"""
Returns one of the keys with Minimal value.
:rtype: str
"""
`