# Python O(1) solution

• use dict `d` for (k,v) dictionary
use dict `fd` for (freq, (tail_node,head_node)) dictionary
use ref `tail` for LFU tail
use int `minf` for storing smallest freq

notice: if over capacity, delete before insertion

``````class Node:
def __init__(self, key, val):
self.key = key
self.val = val
self.f = 1
self.next = None
self.prev = None

def connect(self, nextnode):
self.next = nextnode
if nextnode:
nextnode.prev = self

class LFUCache(object):
def __init__(self, capacity):
"""
:type capacity: int
"""
self.cap = capacity
self.tail = None
self.d = {}
self.fd = {}
self.minf = 0
self.size = 0

def get(self, key):
"""
:type key: int
:rtype: int
"""
if key not in self.d:
return -1
node = self.d[key]
self.hit(node)
return node.val

def put(self, key, value):
"""
:type key: int
:type value: int
:rtype: void
"""
if self.cap == 0:
return
if key in self.d:
node = self.d[key]
self.hit(node)
node.val = value

else:

self.size += 1

if self.size > self.cap:
self.remove(tail)
del self.d[tail.key]

if tail.next:
self.tail = tail.next

self.size -= 1

node = Node(key, value)
self.d[key] = node
if not self.tail:
self.tail = node

def hit(self, node):
self.remove(node)

node.f += 1

if self.tail == node:
if node.f - 1 in self.fd:
self.tail = self.fd[node.f - 1][0]
else:
self.tail = self.fd[node.f][0]

def remove(self, node):
f = node.f
if ftail == node:
ftail = node.next
if ftail:
ftail.prev = None
if node.prev:
node.prev.connect(node.next)
if not ftail and not fhead:
del self.fd[f]
if f == self.minf:
self.minf = 0

else:

f = node.f
if self.minf == 0 or f < self.minf:
self.minf = f
if f in self.fd:
else:
ftail = node
node.prev = None
node.next = None
self.fd[f] = (ftail, node)

# Your LFUCache object will be instantiated and called as such:
# obj = LFUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
``````

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