Implement the Least Recently Used | LRU Cache | Leetcode | Using Map

Implement the Least Recently Used (LRU) cache class LRUCache. The class should support the following operations

• LRUCache(int capacity) Initialize the LRU cache of size capacity.
• int get(int key) Return the value corresponding to 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 introduction of the new pair causes the cache to exceed its capacity, remove the least recently used key.

A key is considered used if a get or a put operation is called on it.

Ensure that get and put each run in O(1)

O(1) average time complexity.

Example 1:

Input:
["LRUCache", [2], "put", [1, 10],  "get", [1], "put", [2, 20], "put", [3, 30], "get", [2], "get", [1]]

Output:
[null, null, 10, null, null, 20, -1]

Explanation:
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 10);  // cache: {1=10}
lRUCache.get(1);      // return 10
lRUCache.put(2, 20);  // cache: {1=10, 2=20}
lRUCache.put(3, 30);  // cache: {2=20, 3=30}, key=1 was evicted
lRUCache.get(2);      // returns 20 
lRUCache.get(1);      // return -1 (not found)

class LRUCache {
    /**
     * @param {number} capacity
     */
    constructor(capacity) {}

    /**
     * @param {number} key
     * @return {number}
     */
    get(key) {}

    /**
     * @param {number} key
     * @param {number} value
     * @return {void}
     */
    put(key, value) {}
}

let's take this and brainstorm our implementation part:

get(key)

1. If the key exists, return its value and mark it as recently used.
2. If the key does not exist, return -1.
3. If the key exists:
4. Mark the key as recently used:
5. In a Map, remove the key and reinsert it , to refresh its order.
6. Return its value.
7. If the key does not exist:
8. Return -1.

put(key, value)

1. Add or update a key-value pair in the cache.
2. If the cache exceeds its capacity, remove the least recently used key before adding a new one.
3. If the key exists:
4. Update its value and mark it as recently used (refresh its order).
5. If the key does not exist:
6. Check if the cache has reached its capacity:
7. If yes, remove the least recently used key (the first key in the Map).
8. Insert the new key-value pair into the cache.

class LRUCache {
    /**
     * @param {number} capacity
     */
    constructor(capacity) {
        this.cache = new Map()
        this.capacity = capacity
    }

 \
    get(key) {
/*
If the key exists,return its value and mark it as recently used.
If the key does not exist, return -1.
*/
        if (!this.cache.get(key)) {
            return -1
        }

// how to mark the key as recently used?
// order in the map, early on has least used, and later is used more recently

        const value = this.cache.get(key)
        this.cache.delete(key)
        this.cache.set(key, value)
        return value
    }


    put(key, value) {
/*
Add or update a key-value pair in the cache,and update the order
If the cache exceeds its capacity, remove the least recently used key before adding a new one.
*/
        if(this.cache.has(key)){
            this.cache.delete(key)
        }else if(this.cache.size >= this.capacity){
const leastRecentlyUsedKey = this.cache.keys().next().value
            this.cache.delete(leastRecentlyUsedKey)
        }
        this.cache.set(key, value)
    }
}

         

The Map object in JavaScript is a powerful and versatile data structure that has several unique properties, making it ideal for problems like the LRU Cache and many others.

Let's break down its nature, advantages, and some ideas we can use beyond the LRU Cache.

Nature of Map

This question a

• Key-Value Storage A Map stores key-value pairs
• 
  

1. Unlike plain JavaScript objects ({}), the keys in a Map can be any data type—strings, numbers, objects, or even functions

const map = new Map();
map.set('key1', 'value1'); // Key is a string
map.set(123, 'value2');  // Key is a number
map.set({ id: 1 }, 'value3'); // Key is an object

console.log(map.get('key1')); // Output: value1
console.log(map.get(123));  // Output: value2

• .Preserves Insertion Order: The Map maintains the insertion order of keys. This means:

1. The first key added will always come first when iterating over the Map.
2. When you delete and re-add a key, it moves to the end of the order.
3. This is why it's useful for tracking the Least Recently Used (LRU) item in the LRU Cache problem.

const map = new Map();
map.set(1, 'A');
map.set(2, 'B');
map.set(3, 'C');
console.log([...map.keys()]); // Output: [1, 2, 3]


map.delete(2);
map.set(2, 'B');
console.log([...map.keys()]); // Output: [1, 3, 2]

This question can also be solved using double linked list which we will cover in next thread.