# LRU Cache LeetCode Solution

Here, We see LRU Cache LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

# List of all LeetCode Solution

## Problem Statement

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.

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

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

## LRU Cache LeetCode SolutionC++

``````class LRUCache
{
public:
list<pair<int,int>> l;
unordered_map<int,list<pair<int, int>>::iterator> m;
int size;
LRUCache(int capacity)
{
size=capacity;
}
int get(int key)
{
if(m.find(key)==m.end())
return -1;
l.splice(l.begin(),l,m[key]);
return m[key]->second;
}
void put(int key, int value)
{
if(m.find(key)!=m.end())
{
l.splice(l.begin(),l,m[key]);
m[key]->second=value;
return;
}
if(l.size()==size)
{
auto d_key=l.back().first;
l.pop_back();
m.erase(d_key);
}
l.push_front({key,value});
m[key]=l.begin();
}
};```Code language: PHP (php)```

## LRU Cache LeetCode SolutionJava

``````class LRUCache {
class Node {
int key;
int val;
Node prev;
Node next;
Node(int key, int val) {
this.key = key;
this.val = val;
}
}
Node head = new Node(-1, -1);
Node tail = new Node(-1, -1);
int cap;
HashMap<Integer, Node> m = new HashMap<>();

public LRUCache(int capacity) {
cap = capacity;
}
newnode.next = temp;
temp.prev = newnode;
}
private void deleteNode(Node delnode) {
Node prevv = delnode.prev;
Node nextt = delnode.next;
prevv.next = nextt;
nextt.prev = prevv;
}

public int get(int key) {
if (m.containsKey(key)) {
Node resNode = m.get(key);
int ans = resNode.val;
m.remove(key);
deleteNode(resNode);
return ans;
}
return -1;
}

public void put(int key, int value) {
if (m.containsKey(key)) {
Node curr = m.get(key);
m.remove(key);
deleteNode(curr);
}
if (m.size() == cap) {
m.remove(tail.prev.key);
deleteNode(tail.prev);
}
}
}```Code language: JavaScript (javascript)```

## LRU Cache LeetCode SolutionJavaScript

``````var LRUCache = function(capacity) {
this._capacity = capacity;
this._count = 0;
this._tail = null;
this._hashTable = {};
};

LRUCache.prototype.get = function(key) {
if (this._hashTable[key]) {
const { value } = this._hashTable[key];
const { prev, next } = this._hashTable[key];
if (prev) { prev.next = next; }
if (next) { next.prev = prev || next.prev; }
if (this._tail === this._hashTable[key]) {
this._tail = prev || this._hashTable[key];
}
this._hashTable[key].prev = null;
}
return value;
}
return -1;
};

LRUCache.prototype.put = function(key, value) {
if (this._hashTable[key]) {
this._hashTable[key].value = value;
this.get(key);
} else {
this._hashTable[key] = { key, value, prev: null, next: null };
}
if (!this._tail) {
this._tail = this._hashTable[key];
}
this._count += 1;
}
if (this._count > this._capacity) {
let removedKey = this._tail.key;
if (this._tail.prev) {
this._tail.prev.next = null;
this._tail = this._tail.prev;
this._hashTable[removedKey].prev = null;
}
delete this._hashTable[removedKey];
this._count -= 1;
}
};```Code language: JavaScript (javascript)```

## LRU Cache LeetCode SolutionPython

``````class LRUCache:
class Node:
def __init__(self, key, val):
self.key = key
self.val = val
self.prev = None
self.next = None

def __init__(self, capacity):
self.cap = capacity
self.tail = self.Node(-1, -1)
self.m = {}

newnode.next = temp
temp.prev = newnode

def deleteNode(self, delnode):
prevv = delnode.prev
nextt = delnode.next
prevv.next = nextt
nextt.prev = prevv

def get(self, key):
if key in self.m:
resNode = self.m[key]
ans = resNode.val
del self.m[key]
self.deleteNode(resNode)
return ans
return -1

def put(self, key, value):
if key in self.m:
curr = self.m[key]
del self.m[key]
self.deleteNode(curr)
if len(self.m) == self.cap:
del self.m[self.tail.prev.key]
self.deleteNode(self.tail.prev)