# Simple and Self-explained Python Solution (2 hash maps, no linked list)

• Instead of using a linked list, I use a `minfreq` to keep track of the LFU frequency.

`d`: Store key -> [freq, value] pair.
`freq`: Store freq -> OrderedDict(key1, key2, ...) # Here I use an OrderedDict as an ordered set to store the keys in the same frequency so that it contains LRU functionality if we use `.popitem(last=False)` method.
Function `touch`: update `freq` (frequency increased by 1) whenever we read or write a key.

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

def __init__(self, capacity):
"""
:type capacity: int
"""
self.capacity = capacity
self.usage = 0
self.d = {}
self.freq = {}
self.minfreq = 0

def get(self, key):
"""
:type key: int
:rtype: int
"""
if key in self.d:
self.touch(key)
# return value
return self.d[key][1]
return -1

def put(self, key, value):
"""
:type key: int
:type value: int
:rtype: void
"""
if not self.capacity:
return
if key in self.d: # old key
self.d[key][1] = value # update value
self.touch(key)   # update freq in the system
else: # new key
if self.usage >= self.capacity:
# remove a key from the cache first before add the new key
deletedkey = self.freq[self.minfreq].popitem(last=False)[0] # get the LFU key
self.d.pop(deletedkey) # delete the key in self.d
if not self.freq[self.minfreq]:
self.freq.pop(self.minfreq)
self.usage -= 1
self.d[key] = [1,value] # add to self.d
if not 1 in self.freq:
self.freq[1] = collections.OrderedDict()
self.freq[1][key] = 1   # add to self.freq
self.usage += 1
self.minfreq = 1

def touch(self, key):
# add freq by one for key
# pop key from freq[old_freq]
old_freq = self.d[key][0]
self.freq[old_freq].pop(key)
# delete freq[old_freq] if it's empty
if not self.freq[old_freq]:
self.freq.pop(old_freq)
# if minfreq is affected, update its value
if self.minfreq == old_freq:
self.minfreq += 1
# add key to new_freq, if freq[new_freq] does not exist, create one
new_freq = old_freq + 1
if not new_freq in self.freq:
self.freq[new_freq] = collections.OrderedDict()
self.freq[new_freq][key] = 1
# update the freq in self.d
self.d[key][0] += 1

# 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.