Jones Codes

Leetcode Problem: LRU Cache

4 min read

Today I worked on the leetcode problem LRU Cache. Sometimes these problems feel like the real world application is absent. Today I was pleasantly surprised as I can imagine myself using this in a real application. Implementing caching can greatly improve server performance and reduce database queries. Learning how to create a Least Recently Used policy is a valuable concept to understand. Cache_replacement_policies Wiki

LeetCode Problem Prompt:

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.

This is the initial code provided.

/**
 * @param {number} capacity
 */
var LRUCache = function(capacity) {
    
};
 
/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
    
};
 
/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
    
};
 
/** 
 * Your LRUCache object will be instantiated and called as such:
 * var obj = new LRUCache(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */

While working on this problem I became more familiar with the Map datatype in Javascript. In most Javascript codebases I have interacted with, the code uses the basic types such as array, object, string, boolean, number. It is interesting why to ponder on why this is the case. ----------

The Map data type is different than a normal object in that it preserves the order of insertion. MDN. It comes with several built in methods like

clear(), delete(), entries(), forEach(), get(), has(), keys(), set() and values()

/**
 * @param {number} capacity
 */
var LRUCache = function(capacity) {
    this.capacity = capacity
    this.map = new Map()
};
 
/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
    if (!this.map.has(key)) return -1
    const value = this.map.get(key);
    this.map.delete(key)
    this.map.set(key, value)
    return value
};
 
/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
    if (this.map.has(key)) {
        this.map.delete(key)
    }
    this.map.set(key, value)
    if (this.map.size > this.capacity) {
        const first = this.map.keys().next().value
        this.map.delete(first)
    }
};
 
/** 
 * Your LRUCache object will be instantiated and called as such:
 * var obj = new LRUCache(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */

Step-by-step

this.map.keys() Returns an iterator of the keys in insertion order. Since we’re using a Map, JavaScript guarantees that iteration preserves the order in which keys were added.

.next() Advances the iterator to the first element (the oldest key in this case). It returns an object like: { value: <firstKey>, done: false }

.value Extracts the actual key value.

So at this point, firstKey is the least recently used key.

this.map.delete(firstKey) Removes that key-value pair from the map, freeing up space.

Why this Works

Every time you get or put, you delete the key first and re-insert it at the end of the Map. That pushes it to the “most recently used” position. The first key in the iteration order is always the “least recently used.”

Therefore the end of map = most recently used and the start of the map = least recently used (the one we delete when over capacity)

Lets talk Big O

  1. Map operations in JavaScript

this.map.has(key) → O(1)

this.map.get(key) → O(1)

this.map.set(key, value) → O(1)

this.map.delete(key) → O(1)

JavaScript’s Map is implemented as a hash map, so these lookups, inserts, and deletes are constant-time on average.

  1. Moving an item to the “most recently used” spot this.map.delete(key); this.map.set(key, value);

Both delete and set are O(1), so updating recency is O(1).

  1. Evicting the least recently used key
const first = this.map.keys().next().value;
this.map.delete(first);

this.map.keys() creates an iterator,

.next() gives you the first key in constant time (no scanning),

.delete(first) is O(1).

So eviction is also O(1).

Conclusion

get(key) → one has, one get, one delete, one set → all O(1).

put(key, value) → at most one delete, one set, and possibly one eviction (.keys().next() + delete) → all O(1).

Thus, every cache operation runs in constant time on average.

If you implemented LRU with a plain JS object, you wouldn’t be able to maintain insertion order efficiently — you’d need a doubly linked list + hash map combo to guarantee O(1). The neat trick here is that JavaScript’s Map already preserves insertion order, so you get O(1) without writing a linked list yourself.

Graph View