# [LC] 146. LRU Cache

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the `LRUCache` class:

• `LRUCache(int capacity)` Initialize the LRU cache with positive size `capacity`.
• `int get(int key)` Return the value of the `key` if the key exists, otherwise return `-1`.
• `void put(int key, int value)` Update the value of the `key` if the `key` exists. Otherwise, add the `key-value` pair to the cache. If the number of keys exceeds the `capacity` from this operation, evict the least recently used key.

Could you do `get` and `put` in `O(1)` time complexity?

## Approach

Although I’m crazy about the system design, it was my first coding without any reference, and accepted one. I used the priority queue as our basic data structure. To be specific, Max Heap is used for implementing LRU Cache. We can simply save a tuple of (time, key, value) in the max heap. in here, the key is the time which is created by time.time() that returns Epoch time (float). So, I was thinking I can use it as a key and it will be sorted out whenever the tuple is changed. So, every put/get action need at least O(logN) time.

``````import heapq
import time

class LRUCache:
cache = []
size = 0
def __init__(self, capacity: int):
self.cache = []
self.size = capacity

def get(self, key: int) -> int:
if len(self.cache) == 0:
return -1

if key in [k for t,k,v in self.cache]:
for i,c in enumerate(self.cache):
t,k,v = c
if k == key:
t = time.time()
self.cache[i] = (t,k,v)
heapq.heapify(self.cache)
return v

return -1

def put(self, key: int, value: int) -> None:

if key not in [k for t,k,v in self.cache] and len(self.cache) == self.size:
heapq.heappop(self.cache)

found = False
if key in [k for t,k,v in self.cache]:
for i,c in enumerate(self.cache):
t,k,v = c
if k == key:
t = time.time()
self.cache[i] = (t,k,value)
found = True
break
t = time.time()
heapq.heappush(self.cache, (t, key, value))
else:
heapq.heapify(self.cache)

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

I think it’s okay but the follow-up request gets and puts in O(1) time complexity. I think without a heap, there is no way to sort the cache. The trick is the amortized analysis. If we make a max heap whenever the cache is full, it requires just a few times except every time we put a different key, which has not happened frequently. So, in the revised code, I do the heapify only when the cache is full.

``````import heapq
import time

class LRUCache:
cache = []
size = 0
def __init__(self, capacity: int):
self.cache = []
self.size = capacity

def get(self, key: int) -> int:
if len(self.cache) == 0:
return -1

if key in [k for t,k,v in self.cache]:
for i,c in enumerate(self.cache):
t,k,v = c
if k == key:
t = time.time()
self.cache[i] = (t,k,v)
heapq.heapify(self.cache)
return v

return -1

def put(self, key: int, value: int) -> None:

if key not in [k for t,k,v in self.cache] and len(self.cache) == self.size:
heapq.heappop(self.cache)

found = False
if key in [k for t,k,v in self.cache]:
for i,c in enumerate(self.cache):
t,k,v = c
if k == key:
t = time.time()
self.cache[i] = (t,k,value)
found = True
break
t = time.time()
heapq.heappush(self.cache, (t, key, value))
else:
heapq.heapify(self.cache)

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

I first use for loop to find the cache by key but I soon realized that it does not match the follow-up question because every time when I put or get, I need actual index by key and I used for loop to find the index which requires O(N) So, revised #1 is O(N), not O(1)

So, I thought that O(1) is required some kind of max heap + hashmap structure. When putting the item, hashmap saves the index (in here, I just simply save size of the cache -1 since I always add item in the end), And when I need heapify again, I should update the index which requires O(N). So, the worst case of put() is logN + N but it will be working O(1) based on the amortized analysis.

``````import heapq
import time

class LRUCache:
cache = []
size = 0
m = {}
def __init__(self, capacity: int):
self.cache = []
self.m = {}
self.size = capacity

def get(self, key: int) -> int:
if len(self.cache) == 0:
return -1

if key in self.m:
t,k,v = self.cache[self.m[key]]
t = time.time()
self.cache[self.m[key]] = (t,k,v)
return v

return -1

def put(self, key: int, value: int) -> None:
if key not in [k for t,k,v in self.cache] and len(self.cache) == self.size:
heapq.heapify(self.cache)
t,k,v = heapq.heappop(self.cache)
self.m.pop(k)
t = time.time()
self.cache.append((t, key, value))
for i,c in enumerate(self.cache):
t,k,v = c
self.m[k] = i
elif key in self.m:
t,k,v = self.cache[self.m[key]]
t = time.time()
self.cache[self.m[key]] = (t,k,value)

else:
t = time.time()
self.cache.append((t, key, value))
self.m[key] = len(self.cache) - 1``````

## Submission

Runtime: 2508 ms, faster than 5.06% of Python3 online submissions for LRU Cache.

Memory Usage: 23.5 MB, less than 62.47% of Python3 online submissions for LRU Cache.

## Time/Space Complexity

O(1) (based on amortized analysis)