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

Example 1:

`Input["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"][[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]Output[null, null, null, 1, null, -1, null, -1, 3, 4]ExplanationLRUCache lRUCache = new LRUCache(2);lRUCache.put(1, 1); // cache is {1=1}lRUCache.put(2, 2); // cache is {1=1, 2=2}lRUCache.get(1);    // return 1lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}lRUCache.get(2);    // returns -1 (not found)lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}lRUCache.get(1);    // return -1 (not found)lRUCache.get(3);    // return 3lRUCache.get(4);    // return 4`

Constraints:

• `1 <= capacity <= 3000`
• `0 <= key <= 3000`
• `0 <= value <= 104`
• At most `3 * 104` calls will be made to `get` and `put`.

Intuition

The problem can be solved with a hashmap that keeps track of the keys and its values in the double linked list. That results in O(1) time for `put` and `get` operations and allows to remove the first added node in O(1) time as well.

One advantage of double linked list is that the node can remove itself without other reference. In addition, it takes constant time to add and remove nodes from the head or tail.

One particularity about the double linked list implemented here is that there are pseudo head and pseudo tail to mark the boundary, so that we don’t need to check the `null` node during the update.

Code

Complexity Analysis

• Time complexity : O(1) both for `put` and `get`.
• Space complexity : O(capacity) since the space is used only for a hashmap and double linked list with at most `capacity + 1` elements.

Full Stack Programmer, love to solve problem’s during free time.

## More from Jaydeep

Full Stack Programmer, love to solve problem’s during free time.