> For the complete documentation index, see [llms.txt](https://chunhthanhde.gitbook.io/leetcode-top-interview/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://chunhthanhde.gitbook.io/leetcode-top-interview/topic-8-linked-list/067-lru-cache.md).

# 146. LRU Cache 🔗

**Difficulty**: `Medium` - **Tags**: `Design`, `Linked List`, `Hash Table`

[LeetCode Problem Link](https://leetcode.com/problems/lru-cache/)

***

## Problem Statement 📜

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the `LRUCache` class:

1. `LRUCache(int capacity)`: Initialize the LRU cache with positive size capacity.
2. `int get(int key)`: Return the value of the key if the key exists, otherwise return `-1`.
3. `void put(int key, int value)`:
   * Update the value of the key if it exists.
   * Add the key-value pair if the key does not exist.
   * If the number of keys exceeds the capacity, evict the least recently used key.

**Constraints**:

* The functions `get` and `put` must run in **O(1)** average time complexity.

***

## Examples 🌟

🔹 **Example 1**:

**Input**:

```plaintext
["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**:

```plaintext
[null, null, null, 1, null, -1, null, -1, 3, 4]
```

**Explanation**:

```plaintext
LRUCache 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 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2);    // return -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 3
lRUCache.get(4);    // return 4
```

***

## Constraints ⚙️

* `1 <= capacity <= 3000`
* `0 <= key <= 10⁴`
* `0 <= value <= 10⁵`
* At most `2 * 10⁵` calls will be made to `get` and `put`.

***

## Solution 💡

Use a combination of:

1. **HashMap**: For O(1) access to key-value pairs.
2. **Doubly Linked List**: For maintaining the order of usage (most recently used to least recently used).

***

### Java Solution

```java
import java.util.HashMap;

class LRUCache {
    private class Node {
        int key, value;
        Node prev, next;

        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private final int capacity;
    private final HashMap<Integer, Node> map;
    private final Node head, tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
        this.head = new Node(0, 0);
        this.tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            remove(node);
            insert(node);
            return node.value;
        }
        return -1;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            remove(map.get(key));
        }
        if (map.size() == capacity) {
            remove(tail.prev);
        }
        insert(new Node(key, value));
    }

    private void remove(Node node) {
        map.remove(node.key);
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void insert(Node node) {
        map.put(node.key, node);
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
        node.prev = head;
    }
}
```

***

## Explanation of the Solution

1. **Node Definition**:
   * Each node stores a key-value pair.
   * Nodes are linked in both directions to allow quick removal.
2. **HashMap**:
   * Maps keys to nodes for O(1) access.
3. **Doubly Linked List**:
   * The head points to the most recently used node.
   * The tail points to the least recently used node.
4. **Operations**:
   * `get`: Move the node to the head of the list.
   * `put`: Add the node to the head. If the cache exceeds capacity, remove the node at the tail.

***

## Time Complexity ⏳

* **O(1)** for both `get` and `put` operations.

## Space Complexity 💾

* **O(n)** for storing `n` key-value pairs in the HashMap and Doubly Linked List.

***

## Follow-up 🧐

The solution is optimized for LRU Cache implementation with constant time complexity and minimal space usage. Further optimizations could involve concurrent data structures for multi-threaded environments.

You can find the full solution [here](https://github.com/ChunhThanhDe/Leetcode-Top-Interview/blob/main/Topic%208%20Linked%20List/067%20LRU%20Cache/Solution.java).


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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, and the optional `goal` query parameter:

```
GET https://chunhthanhde.gitbook.io/leetcode-top-interview/topic-8-linked-list/067-lru-cache.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

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.