146. LRU Cache LeetCode Solution

In this guide, you will get 146. LRU Cache LeetCode Solution with the best time and space complexity. The solution to LRU Cache problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
LRU Cache solution in C++
LRU Cache solution in Java
LRU Cache solution in Python
Additional Resources

Problem Statement of 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.

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(1); // return -1 (not found)
lRUCache.get(3); // return 3
lRUCache.get(4); // return 4

Constraints:

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

Complexity Analysis

Time Complexity: O(1)
Space Complexity: O(\texttt{capacity})

146. LRU Cache LeetCode Solution in C++

struct Node {
  int key;
  int value;
  shared_ptr<Node> prev;
  shared_ptr<Node> next;
};

class LRUCache {
 public:
  LRUCache(int capacity) : capacity(capacity) {
    join(head, tail);
  }

  int get(int key) {
    const auto it = keyToNode.find(key);
    if (it == keyToNode.cend())
      return -1;

    shared_ptr<Node> node = it->second;
    remove(node);
    moveToHead(node);
    return node->value;
  }

  void put(int key, int value) {
    if (const auto it = keyToNode.find(key); it != keyToNode.cend()) {
      shared_ptr<Node> node = it->second;
      node->value = value;
      remove(node);
      moveToHead(node);
      return;
    }

    if (keyToNode.size() == capacity) {
      shared_ptr<Node> lastNode = tail->prev;
      keyToNode.erase(lastNode->key);
      remove(lastNode);
    }

    moveToHead(make_shared<Node>(key, value));
    keyToNode[key] = head->next;
  }

 private:
  const int capacity;
  unordered_map<int, shared_ptr<Node>> keyToNode;
  shared_ptr<Node> head = make_shared<Node>(-1, -1);
  shared_ptr<Node> tail = make_shared<Node>(-1, -1);

  void join(shared_ptr<Node> node1, shared_ptr<Node> node2) {
    node1->next = node2;
    node2->prev = node1;
  }

  void moveToHead(shared_ptr<Node> node) {
    join(node, head->next);
    join(head, node);
  }

  void remove(shared_ptr<Node> node) {
    join(node->prev, node->next);
  }
};
/* code provided by PROGIEZ */

146. LRU Cache LeetCode Solution in Java

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

class LRUCache {
  public LRUCache(int capacity) {
    this.capacity = capacity;
  }

  public int get(int key) {
    if (!keyToNode.containsKey(key))
      return -1;

    Node node = keyToNode.get(key);
    cache.remove(node);
    cache.add(node);
    return node.value;
  }

  public void put(int key, int value) {
    if (keyToNode.containsKey(key)) {
      keyToNode.get(key).value = value;
      get(key);
      return;
    }

    if (cache.size() == capacity) {
      Node lastNode = cache.iterator().next();
      cache.remove(lastNode);
      keyToNode.remove(lastNode.key);
    }

    Node node = new Node(key, value);
    cache.add(node);
    keyToNode.put(key, node);
  }

  private int capacity;
  private Set<Node> cache = new LinkedHashSet<>();
  private Map<Integer, Node> keyToNode = new HashMap<>();
}
// code provided by PROGIEZ

146. LRU Cache LeetCode Solution in Python

class Node:
  def __init__(self, key: int, value: int):
    self.key = key
    self.value = value
    self.prev = None
    self.next = None


class LRUCache:
  def __init__(self, capacity: int):
    self.capacity = capacity
    self.keyToNode = {}
    self.head = Node(-1, -1)
    self.tail = Node(-1, -1)
    self.join(self.head, self.tail)

  def get(self, key: int) -> int:
    if key not in self.keyToNode:
      return -1

    node = self.keyToNode[key]
    self.remove(node)
    self.moveToHead(node)
    return node.value

  def put(self, key: int, value: int) -> None:
    if key in self.keyToNode:
      node = self.keyToNode[key]
      node.value = value
      self.remove(node)
      self.moveToHead(node)
      return

    if len(self.keyToNode) == self.capacity:
      lastNode = self.tail.prev
      del self.keyToNode[lastNode.key]
      self.remove(lastNode)

    self.moveToHead(Node(key, value))
    self.keyToNode[key] = self.head.next

  def join(self, node1: Node, node2: Node):
    node1.next = node2
    node2.prev = node1

  def moveToHead(self, node: Node):
    self.join(node, self.head.next)
    self.join(self.head, node)

  def remove(self, node: Node):
    self.join(node.prev, node.next)
 # code by PROGIEZ