Python in O(n) to track least recent (use deque)

  • 1
    def __init__(self, capacity):
        self.size = capacity
        self.dic = {}
        self.order = deque()
    def get(self, key):
        if key not in self.dic:
            return -1
        value = self.dic[key]
        self.order.remove(key) # take O(n)
        self.order.append(key) # O(1)
        return value
    def set(self, key, value):
        if key in self.dic:
            self.order.remove(key) # take O(n)
        elif key not in self.dic and len(self.dic) == self.size:
            tmp = self.order.popleft() #O(1) remove the least recently
            self.dic.pop(tmp) # remove least recently from dict
        self.order.append(key) # O(1)    
        self.dic[key] = value

Log in to reply

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