# 146. LRU Cache

### Description

Design a data structure that follows the constraints of a [**Least Recently Used (LRU) cache**](https://en.wikipedia.org/wiki/Cache_replacement_policies#LRU).

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.

### Constraints

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

### Approach

### Links

* [GeeksforGeeks](https://www.geeksforgeeks.org/lru-cache-implementation/)
* [Leetcode](https://leetcode.com/problems/lru-cache/)
* [ProgramCreek](https://www.programcreek.com/2013/03/leetcode-lru-cache-java/)
* YouTube

### **Examples**

{% tabs %}
{% tab title="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]

**Explanation:**

<div align="left"><img src="/files/-MHW3vRNt6q8F2q9ghKG" alt=""></div>
{% endtab %}
{% endtabs %}

### **Solutions**

{% tabs %}
{% tab title="Solution 1" %}

```java
/**
 * Time complexity : O(1) both for put and get since all operations with 
 *    ordered dictionary. get/in/set/move_to_end/popitem 
 *    (get/containsKey/put/remove) are done in a constant time.
 * Space complexity : O(capacity) since the space is used only for an 
 *    ordered dictionary with at most capacity + 1 elements.
 */

class LRUCache extends LinkedHashMap<Integer, Integer> {
    
    private int capacity;

    public LRUCache(int capacity) {
        super(capacity, 0.75F, true);
        this.capacity = capacity;
    }
    
    public int get(int key) {
        return super.getOrDefault(key, -1);
    }
    
    public void put(int key, int value) {
        super.put(key, value);
    }
    
    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity; 
    }
}

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

{% endtab %}

{% tab title="Solution 2" %}

```java
/**
 * Time complexity : 
 * Space complexity : 
 */

class LRUCache {
    
    class Node {
        int key;
        int value;
        Node prev;
        Node next;
        
        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    
    private int capacity;
    private Node head;
    private Node tail;
    private Map<Integer, Node> cache;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap();
    }
    
    public int get(int key) {
        Node node = cache.get(key);
        if(node == null) return -1;
        
        removeNode(node);
        offerNode(node);
        
        return node.value;
    }
    
    public void put(int key, int value) {
        if(cache.containsKey(key)) {
            Node node = cache.get(key);
            node.value = value;

            removeNode(node);
            offerNode(node);
        } else {
            if(cache.size() >= capacity) {
                cache.remove(head.key);
                removeNode(head);
            }
            
            Node node = new Node(key, value);
            offerNode(node);
            cache.put(key, node);
        }
    }
    
    private void offerNode(Node node) {
        if(tail != null) {
            tail.next = node;
        }
        
        node.next = null;
        node.prev = tail;
        tail = node;
        
        if(head == null) {
            head = tail;
        }
    }
    
    private void removeNode(Node node) {
        if(node.prev != null) {
            node.prev.next = node.next;
        } else {
            head = node.next;
        }
        
        if(node.next != null) {
            node.next.prev = node.prev;
        } else {
            tail = node.prev;
        }
    }
}

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

{% endtab %}
{% endtabs %}

### **Follow up**

* &#x20;Could you do `get` and `put` in `O(1)` time complexity?


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://code-snippets.hbamithkumara.com/leetcode/problems/101-200/lru-cache.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.