LRU Cache

Description

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 <= 10⁴
0 <= value <= 10⁵
At most 2¹⁰ calls will be made to get and put.

Idea

After reading the description of this problem, I think most people would find these two important requirements: a) we need to evict the least recently used key, b) The get and put must run in O(1) time complexity.
So let's see how we can solve it with those requirements in mind.
If we only care about the O(1) time complexity, then it's an easy problem. We could just use a regular HashMap to store the keys and values and it will suffice.
How could we solve the least recently used key problem then?
Actually if you think about it, "least recent" implies an "ordered" kind of data structure, right? The most common data structure that implies an order is an array. So let's see if we can solve it using an array.
Suppose at the head of the array we store the most recently used key, and at the tail of the array, we store the least recently used key, will it work?
Actually it won't. Because, let's say, if we access one of the keys in the middle, update its associated value, then we need to move this key to the front after updating its value, because it becomes the most recent item now. And that would be an O(n) time complexity operation, with n being the cache capacity.
So what do we do?
Let's think a bit deeper about what we miss for the above use case. So we need to be able to "insert" a new key in the front, and also "remove" the key from basically any position of the cache with O(1) time complexity. So what kind of data structure would satisfy that? Doubly Linked List (DLL) it is.
Why "doubly" linked list though, can we do with singly? Actually no, because we need to be able to remove a key from any position, that would require us to be able to find the previous and next key in O(1) time, and "singly" linked list won't allow that.
OK, we got "doubly" linked list, to be able to "insert" and "remove" keys, is that enough?
Not quite, we still need to access the keys with O(1) time complexity. That's not too difficult, we can use an additional HashMap for that, the key in the HashMap would be the key itself, the value would be a node in the doubly linked list with the value stored in it.
After all these babbling, you might want to see this data structure with some illustration? I think the same, actually it'll look simiar like below. Note that the order information is stored in the linked list, not in the HashMap.
OK, let's start writing some code.
So in Javascript we don't have a Doubly Linked List in the library, so we have to write it from scratch. Sad, I know. However, it's gonna be a fun exercise though. You'll see, lol.
So what we need is a) a linked list Node data structure, b) a constructor for DLL, c) DLL.insertFront(), d) DLL.prioritize(), e) DLL.pop().
The Node and DLL constructor should be very self-explantory, let's see the rest of them.
DLL.insertFront(): this function basically insert a node into the front of the list. Also if it's a new node, we will increase the size of the list, that's it. I added a newNode param only because the "insertFront" logic is same for inserting a node for a new key and inserting an existing node from the middle of the list, so I refactored it a bit and let me know if it does not make sense to you.
DLL.prioritize(): this function basically remove a node from the middle of the list and insert it into the front. It reuses the DLL.insertFront() logic, and seems pretty logical to me.
DLL.pop(): this is to remove the least recently used key and node when we reach capacity, the code should be very clear. Btw, we return the node is because we need the key information to clear the node in the HashMap too.
Cool, so we have the DLL as our weapon, let's solve the LRUCache.
Actually, I changed my mind. Because, once we have the DLL, the LRUCache code is surprisingly simple. Let me know if you need extra explanation.
And because we only have pointers operation for all the code, there's no loop or anything, so it satifies the O(1) requirement. Not Bad, lol.
Thanks for reading.

Solution

Javascript

// HashMap with Doubly linked list
const LRUCache = function(capacity) {
  this.capacity = capacity;
  this.map = {}; // { key: node }
  this.dll = new DoublyLinkList();
};

LRUCache.prototype.get = function(key) {
  const node = this.map[key];
  if (!node) return -1;
  
  this.dll.prioritize(node);
  return node.val;
};

LRUCache.prototype.put = function(key, value) {
  if (this.map[key]) {
    const node = this.map[key];
    node.val = value;
    this.dll.prioritize(node);
  } else {
    if (this.dll.size == this.capacity) {
      const node = this.dll.pop();
      if (node) delete this.map[node.key];
    }
    const newNode = new Node(key, value);
    this.dll.insertFront(newNode);
    this.map[key] = newNode;
  }
};

const Node = function(key, val) {
  this.key = key;
  this.val = val;
  this.prev = this.next = null;
};

const DoublyLinkList = function() {
  this.head = new Node(); // dummy head
  this.tail = new Node(); // dummy tail
  this.size = 0;
  this.head.next = this.tail;
  this.tail.prev = this.head;
};

DoublyLinkList.prototype.insertFront = function(node, newNode=true) {
  const headNext = this.head.next;
  this.head.next = node;
  node.prev = this.head;
  node.next = headNext;
  headNext.prev = node;
  if (newNode) this.size += 1;
};

DoublyLinkList.prototype.prioritize = function(node) {
  // if one node or node is already at first position
  if (this.size <= 1 || this.head.next == node) return;
  // if node in middle of list, delete this node
  const prevNode = node.prev;
  const nextNode = node.next;
  prevNode.next = nextNode;
  nextNode.prev = prevNode;
  this.insertFront(node, false);
};

DoublyLinkList.prototype.pop = function() {
  if (this.size == 0) return;

  const poppedNode = this.tail.prev;
  const prevNode = poppedNode.prev;
  prevNode.next = this.tail;
  this.tail.prev = prevNode;
  this.size -= 1;
  return poppedNode;
};

References

Least Recently Used (LRU) cache
Least Frequently Used (LFU) cache

any9527/leetcode_146.md

Description

Idea

Solution

Javascript

References