Leetcode # 146. LRU Cache

2023.07.18
deque LeetCode

Solution

Time Complexity: O(capacity)
Space Complexity: O(capacity)
(The input and output generally do not count towards the space complexity.)

class LRUCache:

    def __init__(self, capacity: int):
      self.capacity = capacity
      self.lru_keys = collections.deque()
      self.values = {}

    def get(self, key: int) -> int:
      if key in self.values:
        self.lru_keys.remove(key)
        self.lru_keys.append(key)
        return self.values[key]
      return -1

    def put(self, key: int, value: int) -> None:
      if self.get(key) != -1:
        self.values[key] = value
      else:
        if len(self.lru_keys) == self.capacity:
          removed_key = self.lru_keys.popleft()
          self.values.pop(removed_key)
        self.lru_keys.append(key)
        self.values[key] = value


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

Last Updated on 2023/08/16 by A1go