# leetcode\_146

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

## Solutions

1. **double linked list with hashmap**
2. borrowed from others.
3. Use hash map to get/set item in `O(1)` time.
4. Use double linked list to retain the latest used item in the front and the least used item in the back to evict the leaset used item in `O(1)` time.
   * remove an item in double linked list with it's reference is `O(1)` complexity. (Use map to keep the reference).
   * Thus we need another map to save iterators of each item in double linked list.

```cpp
class LRUCache {
private:
    int size;
    list<int> lru;
    unordered_map<int, list<int>::iterator> mp;
    unordered_map<int, int> kv;

public:
    LRUCache(int capacity) : size(capacity) {}

    int get(int key) {
        if (!kv.count(key))
            return -1;
        else {
            update(key);
            return kv[key];
        }
    }

    void put(int key, int value) {
        if (!kv.count(key) && kv.size() == size) evict();
        update(key);
        kv[key] = value;
    }

    void update(int key) {
        if (kv.count(key)) lru.erase(mp[key]);
        lru.push_front(key);
        mp[key] = lru.begin();
    }

    void evict() {
        kv.erase(lru.back());
        mp.erase(lru.back());
        lru.pop_back();
    }
};

/**
 * 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);
 */
```

Or save `key-value` pair in double linked list and store each node's iterator in a hashmap.

```cpp
class LRUCache {
public:
    using kv = pair<int, int>;
    int cap = 0;
    list<kv> lru;
    unordered_map<int, list<kv>::iterator> m;
    LRUCache(int capacity) : cap(capacity) {

    }

    int get(int key) {
        if (!m.count(key))
            return -1;
        else {
            update(key, m[key]->second);
            return m[key]->second;
        }
    }

    void put(int key, int value) {
        if (lru.size() >= cap && !m.count(key))
            evict();
        update(key, value);
    }

    void evict() {
        if (lru.size()) {
            m.erase(lru.back().first);
            lru.pop_back();
        }
    }

    void update(int key, int value) {
        if (m.count(key))
            lru.erase(m[key]);
        lru.emplace_front(key, value);
        m[key] = lru.begin();
    }
};
```

Or use self-made double linked list.

```cpp
template <typename K, typename V>
struct List {
    using node = List<K, V>;
    K key;
    V val;
    node * prev;
    node * next;
    List(K k = K(0), V v = V(0), node * prev = NULL, node * next = NULL)
    : key(k), val(v), prev(prev), next(next) {}
};

typedef List<int, int> Node;

class LRUCache {
private:
    int size;
    Node * front;
    Node * back;
    unordered_map<int, Node *> mp;

public:
    LRUCache(int capacity) : size(capacity) {
        front = new Node(); back = new Node(); 
        front->next = back; back->prev = front;
    }

    int get(int key) {
        if (!mp.count(key))
            return -1;
        else {
            update(key, mp[key]->val);
            return mp[key]->val;
        }
    }

    void put(int key, int value) {
        if (mp.size() == size && !mp.count(key)) {
            // remove the last node
            Node * node = back->prev;
            node->prev->next = node->next;
            node->next->prev = node->prev;
            mp.erase(node->key);
            delete(node);
        }
        update(key, value);
    }

    void update(int key, int value) {
        Node * head;
        if (mp.count(key)) {
            // remove from the list
            head = mp[key];
            head->prev->next = head->next;
            head->next->prev = head->prev;
            head->val = value;
            head->next = front->next;
            head->prev = front;
        } else
            head = new Node(key, value, front, front->next);
        // insert after the front node.
        front->next->prev = head;
        front->next = head;
        mp[key] = head;
    }

    ~LRUCache() { for (auto & p : mp) delete p.second; }

};

/**
 * 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);
 */
```

Or use builtin object that combined these two data structures in python.

```python
from collections import OrderedDict

class LRUCache(OrderedDict):

    def __init__(self, capacity: int):
        self.size = capacity

    def get(self, key: int) -> int:
        if key not in self:
            return -1
        else:
            # move this item to the end
            self.move_to_end(key)
            return self[key]

    def put(self, key: int, value: int) -> None:
        if len(self) == self.size and key not in self:
            # delete the first element
            self.popitem(last=False)
        if key in self:
            # move to end
            self.move_to_end(key)
        # in orderedDict, new key is automatically append to the end
        self[key] = value


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