# 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.

Follow up:

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.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
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();
    }
};