LRU Cache – Complete Tutorial Hard 0 attempts
GeeksforGeeks ↗

LRU Cache – Complete Tutorial

Hard Stack&Queue GeeksforGeeks

Design and implement a data structure for a Least Recently Used (LRU) cache. It should support get(key) which returns the value if the key exists (otherwise -1), and put(key, value) which inserts or updates the key-value pair. When the cache reaches its capacity, it should invalidate the least recently used item before inserting a new item. Both operations must run in O(1) time.

Example:

capacity=2: put(1,1), put(2,2), get(1)->1, put(3,3), get(2)->-1
Sample Input
—
Sample Output
—
Constraints
  • 1 <= capacity <= 3000
  • 0 <= key <= 10^4
  • 0 <= value <= 10^5
  • At most 2 * 10^5 calls
Topics
Stack&Queue

Approach: HashMap + Ordered Map

Use a Map which maintains insertion order in JavaScript. On get/put, delete and re-insert the key to move it to the end (most recent). On capacity overflow, delete the first key (least recent).

function lruCacheCompleteTutorial(capacity) {
  const cache = new Map();
  return {
    get(key) {
      if (!cache.has(key)) return -1;
      const val = cache.get(key);
      cache.delete(key);
      cache.set(key, val);
      return val;
    },
    put(key, value) {
      cache.delete(key);
      cache.set(key, value);
      if (cache.size > capacity) cache.delete(cache.keys().next().value);
    }
  };
}

Time Complexity: O(1) per operation

Space Complexity: O(capacity)

Saved in this browser only. Private to you.

JavaScript