Super clear O(1) solution using Minimum BASIC data structure (TWO hash tables + ONE doubly linked list)

  • 0

    The basic idea is using ONE doubly linked list to maintain all the data in the cache, wherein each node accommodates a key-value pair. This is the key difference from other solutions using two or 2-d doubly linked list. Storing all the node in a 1-d linked list can avoid many complex 2-d linked list operations, which is error-prone. The nodes that have been accessed for the same frequency are grouped together like in a bucket. And the groups are arranged in the ascending order of frequency in the linked list, where less frequently-accessed node are put behind. So when cache is full, the first node in the linked list will be evicted.

    Two hash tables. One is used for O(1) access from key to its node. And the other is for O(1) access from frequency to boundary node of frequency buckets. More precisely, the boundary nodes are the rightmost node of the buckets, because when we need to add a new node to the bucket, we can easily find the position to add it.

     ------------>    direction of more ```frequent and recent``` access ----->                 
    dummy head <-> n1 <-> n2 <-> n3 <-> n4 <-> n5 <-> n6 <-> n7 <-> dummy tail                      
    buckets        ----------------     ----------------     ---
                      freq = 1             freq = 3       freq = 9
    frequency table f  f[1]=n3              f[3]=n6        f[9]=n7   
    class DLinkNode(object):  # Doubly Linked List Node
        def __init__(self, key, value):
            self.key, self.value = key, value
            self.freq = 0
            self.prev = = None
        def link(self, node):  # Link self and node
            node.prev = self
   = node
        def connect(self, node):  # Connect node behind self
        def disconnect(self):  # Disconnect self from Linked List
   = self.prev
    class LFUCache(object):
        def __init__(self, capacity):
            self.remain = self.capacity = capacity
            self.head = DLinkNode(-1, -1)  # dummy head
            self.tail = DLinkNode(-2, -2)  # dummy tail
   = self.tail
            self.cache = {}  # mapping from key to DLinkNode
            self.freq = {0: self.head}  # mapping from freq to DLinkNode
        def remove(self, key):  # Remove node from linked list
            node = self.cache[key]
            if self.freq[node.freq] is node:  # node is sentinel
                if node.prev.freq == node.freq:
                    self.freq[node.freq] = node.prev  # re-assign sentinel
                else:  # node is the only node in the frequency bucket
                    del self.freq[node.freq]
        def add(self, key):  # add node to freq+1 bucket
            node = self.cache[key]
            f = node.freq = node.freq + 1
            if f in self.freq:  # freq+1 bucket exists
            elif f - 1 in self.freq:  # freq bucket exists
                self.freq[f - 1].connect(node)
            else:  # both buckets not exsits
            self.freq[f] = node
        def move(self, key):
        def get(self, key):
            if key in self.cache:
                return self.cache[key].value
            return -1
        def put(self, key, value):
            if not self.capacity: # handle the 0-capacity case
            if key in self.cache:
                self.cache[key].value = value
                if not self.remain:
                    rm_key =
                    del self.cache[rm_key]
                    self.remain -= 1
                self.cache[key] = DLinkNode(key, value)

  • 0

    Just a side note, for this problem, we need to consider the corner case of cache capacity=0.

Log in to reply

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