LRU Cache

Medium

Problem

Design a Least Recently Used cache with a fixed capacity. get(key) returns the value, or −1 if absent, and marks the key as recently used. put(key, value) inserts or updates the key; when the cache is full, it first evicts the least recently used key. Both operations must be O(1).

Example 1

Input:  capacity 2: put(1,1), put(2,2), get(1), put(3,3), get(2), put(4,4), get(1), get(3), get(4)
Output: 1, -1, -1, 3, 4

Also asked as: LRU Cache Implementationa · Program for Least Recently Used (LRU) Page Replacement algorithm

Test cases

Case 1

Input:    new LRUCache(2)
.put(1, 1)
.put(2, 2)
.get(1)
.put(3, 3)
.get(2)
.put(4, 4)
.get(1)
.get(3)
.get(4)
Expected: [null,null,1,null,-1,null,-1,3,4]

Case 2

Input:    new LRUCache(1)
.put(2, 1)
.get(2)
.put(3, 2)
.get(2)
.get(3)
Expected: [null,1,null,-1,2]

Case 3

Input:    new LRUCache(2)
.get(1)
.put(1, 10)
.put(1, 20)
.get(1)
.put(2, 2)
.put(3, 3)
.get(1)
.get(2)
Expected: [-1,null,null,20,null,null,-1,2]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Hash map + JS Map insertion order

Time O(1) per opSpace O(capacity)

A Map keeps insertion order. On get, delete and re-set the key to mark it most-recent. On put past capacity, delete the first key (least-recent).

class LRUCache {
constructor(capacity) { this.cap = capacity; this.map = new Map(); }
get(key) {
if (!this.map.has(key)) return -1;
const v = this.map.get(key);
this.map.delete(key);
this.map.set(key, v);
return v;
}
put(key, value) {
if (this.map.has(key)) this.map.delete(key);
else if (this.map.size === this.cap) this.map.delete(this.map.keys().next().value);
this.map.set(key, value);
}
}

The "proper" version uses a hash map to nodes of a doubly linked list; same O(1), no reliance on Map ordering.