# 146. LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.

put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

The cache is initialized with a positive capacity.

Could you do both operations in O(1) time complexity?

Example:

LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.put(4, 4);    // evicts key 1
cache.get(3);       // returns 3
cache.get(4);       // returns 4

# Solution

Approach 1: O(n) with an array.

Approach 2: O(1) with a hash table and a list.

# Code (Python)

Approach 2:

class Node:
def __init__(self, key, value):
self.key = key
self.val = value
self.prev = None
self.next = None

class LRUCache:

def __init__(self, capacity: int):
self.capacity = capacity
node = Node(0, 0)
node.prev = node
node.next = node
self.list = node
self.map = {} # {key: Node(value)}

def get(self, key: int) -> int:
if key not in self.map:
return -1
node = self.map[key]
self._remove_node(node)
self._insert_node_front(node)
return node.val

def put(self, key: int, value: int) -> None:
if key in self.map:
self.get(key)
self.map[key].val = value
return
if len(self.map) == self.capacity:
self.map.pop(self.list.prev.key)
self._remove_node(self.list.prev)
node = Node(key, value)
self.map[key] = node
self._insert_node_front(node)

# _remove_node and _insert_node_front are both doubly linked list operations
def _remove_node(self, node):
before, after = node.prev, node.next
before.next = after
after.prev = before

def _insert_node_front(self, node):
before, after = self.list, self.list.next
node.prev = before
node.next = after
before.next = node
after.prev = node

# Code (C++)

Approach 1:

// O(n)
class LRUCache {
private:
vector<pair<int,int>> cache;
int maxSize;
public:
LRUCache(int capacity) {
maxSize = capacity;
}

int get(int key) {
int i = 0;
for (; i < cache.size(); ++i)
{
if (cache[i].first == key)
break;
}
int val = -1;
if (i < cache.size())
{
val = cache[i].second;
cache.erase(cache.begin() + i);
cache.push_back(make_pair(key, val));
}
return val;
}

void put(int key, int value) {
if (get(key) != -1)
{
cache.back().second = value;
}
else
{
if (cache.size() >= maxSize)
cache.erase(cache.begin());
cache.push_back(make_pair(key, value));
}
}
};
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache* obj = new LRUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/

Approach 2:

// O(1)
class LRUCache {
private:
list<pair<int,int>> cache;
unordered_map<int,list<pair<int,int>>::iterator> umap;
int maxSize;
public:
LRUCache(int capacity) {
maxSize = capacity;
}

int get(int key) {
int value = -1;
if (umap.find(key) != umap.end())
{
list<pair<int,int>>::iterator it = umap[key];
value = it->second;
cache.erase(it);
cache.push_back(make_pair(key, value));
umap[key] = --cache.end();
}
return value;
}

void put(int key, int value) {
if (umap.find(key) != umap.end())
{
list<pair<int,int>>::iterator it = umap[key];
cache.erase(it);
}
else if (cache.size() >= maxSize)
{
umap.erase(cache.front().first);
cache.erase(cache.begin());
}
cache.push_back(make_pair(key, value));
umap[key] = --cache.end();
}
};