# Python solution that beats 95.24% submissions

• The key is to swap value of nodes, not nodes themselves.

class AllOne(object):

``````"""Idea:
Use a hash k->node and a linked list node(k, cnt)
to inc a missing, simply prepent to head and hupdate hash
to inc a existed, +1 to cnt and advance node until the next is None or >= cnt
similar to dec
get max return tail
"""

class Node(object):
def __init__(self, k, c):
self.key = k
self.cnt = c
self.next = None
self.prev = None

def __init__(self):
"""
"""
self.map = dict()  # k -> node

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.map:
node = self.Node(key, 1)
self.map[key] = node
else:
else:
node = self.map[key]
node.cnt += 1
while node.next and node.next.cnt < node.cnt:
swap_key = node.next.key
node.key, node.next.key = node.next.key, node.key
node.cnt, node.next.cnt = node.next.cnt, node.cnt
self.map[key] = node.next
self.map[swap_key] = node
node = node.next

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.map:
return
node = self.map[key]
node.cnt -= 1
if node.cnt == 0:
del self.map[key]
if self.head == self.tail == node:
node.next.prev = None
elif self.tail == node:
self.tail = node.prev
node.prev.next = None
else:
node.prev.next = node.next
node.next.prev = node.prev
else:
while node.prev and node.prev.cnt > node.cnt:
swap_key = node.prev.key
node.prev.key, node.key = node.key, node.prev.key
node.prev.cnt, node.cnt = node.cnt, node.prev.cnt
node = node.prev
self.map[key] = node
self.map[swap_key] = node.next

def getMaxKey(self):
"""
Returns one of the keys with maximal value.
:rtype: str
"""
if self.tail:
return self.tail.key
else:
return ""

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