# Python O(1) solution using two dictionary + double linked list

• Inspired by @xiyayan 's solution here

Some notes:
keymap = { key : node }
fremap = { fre : root }, root is circular linked list that connects to self at the beginning. Hence root.next is the head of the list (oldest node, to be removed) and root.prev is the last (newest, to be removed)

If it is LRU problem, we can remove fremap but only the double linked list.

``````class LFUCache(object):

def __init__(self, capacity):
"""
:type capacity: int
"""
self.cap = capacity
self.keymap = {}
self.fremap = {}
self.minfre = 1

def get(self, key):
"""
:type key: int
:rtype: int
"""
if key not in self.keymap:
return -1
else:
node = self.keymap[key]
node.fre += 1
self.ddRemove(node)
if self.fremap[self.minfre].next is self.fremap[self.minfre]:
self.minfre += 1
root = self.fremap.setdefault(node.fre, DoubleListNode(None, None))
return node.value

def put(self, key, value):
"""
:type key: int
:type value: int
:rtype: void
"""
if self.cap == 0: return
if key in self.keymap:
self.keymap[key].value = value
self.get(key)
else:
if len(self.keymap) == self.cap:
root = self.fremap[self.minfre]
keytbd = root.next.key
self.ddRemove(root.next)
del self.keymap[keytbd]
node, self.minfre = DoubleListNode(key, value), 1
root = self.fremap.setdefault(self.minfre, DoubleListNode(None, None))
self.keymap[key] = node

def ddRemove(self, node):
n1, n2 = node.prev, node.next
n1.next, n2.prev = n2, n1
node.prev, node.next = None, None

n1, n2 = tail.prev, tail
node.prev, node.next = n1, n2
n1.next, n2.prev = node, node

class DoubleListNode(object):
def __init__(self, key, value):
self.fre = 1
self.key = key
self.value = value
self.prev = self
self.next = self
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.