# Python all O(1) 99ms solution using Sorted LinkedList and HashMap

• ``````class AllOne(object):

# SHDLL (Super Handy Doubly Linked List)
def __init__(self,prev,next,key,val):
self.prev = prev
self.next = next
self.key = key
self.val = val
def insertBefore(self,node):
# insert given node in front of self
self.prev.next = node
node.prev = self.prev
node.next = self
self.prev = node

def __init__(self):
self.nodes = {}
self.levels = {1:self.TAIL,-1:self.TAIL}

def deleteNode(self,node):
# take given node out of LinkedList
# invariant: given node.val should appear to be correct
node.prev.next = node.next
node.next.prev = node.prev
if self.levels[node.val] == node:
self.levels[node.val] = node.next

def insertNode(self,node):
# insert given node into LinkedList
# invariant: MIN( all the level pointer that points to self.levels[insertPoint] ) = node.val
insertPoint = node.val if node.val in self.levels else -1
self.levels[insertPoint].insertBefore(node)
self.levels[node.val] = node

def inc(self, key):
if key in self.nodes:
node = self.nodes[key]
if node.next.val > node.val or node.next == self.TAIL:
# appear to be in right place
node.val += 1
self.levels[node.val]=node

elif node.next.val == node.val:
self.deleteNode(node)
node.val += 1
self.insertNode(node)
else: # new item
self.nodes[key] = node
self.insertNode(node)

def dec(self, key):
if key not in self.nodes:
return
node = self.nodes[key]

if node.val == 1:
self.deleteNode(node)
del self.nodes[key]
return

if self.levels[node.val-1]!=node:
self.deleteNode(node)
self.levels[node.val-1].insertBefore(node)
else:
self.levels[node.val]=node.next

node.val -= 1
self.levels[node.val] = node

def getMaxKey(self):
return self.TAIL.prev.key

def getMinKey(self):