LeetCode rates this problem Medium.
To solve LeetCode 146 with O(1) get and put, you combine a hash map with a doubly linked list: the hash map gives you constant-time lookups from key to node, and the linked list keeps items ordered by recency so you can evict the least recently used one in constant time. I show two Kotlin implementations below, a from-scratch version using a custom Node class and dummy head/tail sentinels, and a shorter version that subclasses LinkedHashMap and overrides removeEldestEntry. Both meet the O(1) average time requirement and use O(capacity) space.
Why an LRU cache evicts
A cache has a fixed size. When it is full, an eviction policy chooses what to drop. First-In-First-Out (FIFO) drops the oldest item. Least Recently Used (LRU) drops the item that has gone unused the longest, on the idea of temporal locality: data used recently is likely to be used again soon.
LeetCode 146 asks you to build that cache.
The problem
The class has three operations:
LRUCache(int capacity)initialises the cache with a fixed, positive size. Capacity is the maximum number of key-value pairs.int get(int key)returns the value forkey, or -1 if the key is absent. A hit marks the key as recently used.void put(int key, int value)inserts a pair or updates an existing one. Either way, the key becomes recently used. If a new key would exceed capacity, evict the least recently used key first.
Both get and put must run in O(1) average time. The time stays constant, on average, as capacity grows.
The problem’s example uses a cache of capacity 2:
| Operation | Action | Cache State (MRU -> LRU) | Output |
| :---------- | :----------------------------------------------------- | :----------------------- | :----- |
| `put(1, 1)` | Add {1:1}. Cache size is 1. | `{1:1}` | `null` |
| `put(2, 2)` | Add {2:2}. Cache size is 2. | `{2:2}, {1:1}` | `null` |
| `get(1)` | Access {1:1}. It becomes the most recently used (MRU). | `{1:1}, {2:2}` | `1` |
| `put(3, 3)` | Cache is full. Evict LRU item {2:2}. Add {3:3} as MRU. | `{3:3}, {1:1}` | `null` |
| `get(2)` | Key 2 was evicted and is no longer in the cache. | `{3:3}, {1:1}` | `-1` |
| `put(4, 4)` | Cache is full. Evict LRU item {1:1}. Add {4:4} as MRU. | `{4:4}, {3:3}` | `null` |Why one structure is not enough
The O(1) bound rules out using only an array, only a hash map, or only a singly linked list.
An array or a list
An array or a list can keep the most recently used item at one end and the least recently used at the other. Finding a key is a scan, O(n). Moving that item to the front shifts every element in front of it, also O(n).
A hash map alone
A hash map gives O(1) average lookup, insert, and delete. It does not keep order. Finding the least recently used key means scanning every entry, O(n).
A singly linked list
Inserting at the head is O(1). Finding a key means walking from the head, O(n). The least recently used item sits at the tail, and removing the tail means walking to the previous node to update next, also O(n).
No single structure both looks up by key in O(1) and reorders in O(1). The cache uses a hash map and a linked list together.
The design
Pair a hash map with a doubly linked list.
The hash map: O(1) lookups
The map stores each key’s node, not the value. get finds the node without walking the list.
The doubly linked list: O(1) order
The most recently used item sits at the head. The least recently used item sits at the tail.
Each node has next and prev. Once the map hands you the node, you unlink it and move it to the head without a walk. Eviction removes tail.prev.
Two dummy nodes, head and tail, hold no cache data. Every real node sits between them, so a node being added or removed always has neighbours.
Every operation updates the map and the list together.
get and put
Both operations touch the map and the list.
get(key)
get reads a value and moves that node to the most-recent end.
- Check whether
keyis in the map. - If it is missing, return
-1. - If it is present, take the
nodefrom the map, move it to the head, and return thevaluestored in the node. The move unlinks the node, then inserts it at the head.
put(key, value)
put updates a key that is already stored or inserts a key that is not, and evicts when the cache is over capacity.
- Check whether
keyis in the map. - If it is present, take the
node, write the newvalue, and move the node to the head. - If it is missing, create a node with that key and value, insert the node at the head, and map the key to the node.
- If the size now exceeds
capacity, the least recently used node is the one just before the dummy tail. Remove its key from the map and remove the node from the list.
After every operation, the map’s keys are exactly the nodes in the list, ordered from most recent to least recent.
A Kotlin list and map
The first version uses a Node, a MutableMap, and dummy head and tail nodes.
The dummies are non-null, so insertion and removal always sit between two neighbours. There is no separate empty-list case.
class LRUCache(private val capacity: Int) {
// Inner class to represent a node in the doubly linked list
private class Node(
var key: Int,
var value: Int,
var prev: Node? = null,
var next: Node? = null
)
// The cache map for O(1) key-to-node lookup
private val cache: MutableMap<Int, Node> = HashMap()
// Dummy head and tail nodes to simplify list manipulation
private val head: Node = Node(-1, -1)
private val tail: Node = Node(-1, -1)
init {
// Initialize the doubly linked list with dummy nodes
head.next = tail
tail.prev = head
}
// Helper function to remove a node from the list
private fun removeNode(node: Node) {
val prevNode = node.prev
val nextNode = node.next
prevNode?.next = nextNode
nextNode?.prev = prevNode
}
// Helper function to add a node to the head of the list (MRU position)
private fun addToHead(node: Node) {
node.prev = head
node.next = head.next
head.next?.prev = node
head.next = node
}
fun get(key: Int): Int {
val node = cache[key]
if (node == null) {
// Key not found in cache
return -1
} else {
// Key found, move the node to the head to mark it as most recently used
removeNode(node)
addToHead(node)
return node.value
}
}
fun put(key: Int, value: Int) {
val node = cache[key]
if (node!= null) {
// Key already exists, update its value and move it to the head
node.value = value
removeNode(node)
addToHead(node)
} else {
// Key does not exist, create a new node
val newNode = Node(key, value)
cache[key] = newNode
addToHead(newNode)
// If adding the new node exceeds capacity, evict the LRU item
if (cache.size > capacity) {
val lruNode = tail.prev
if (lruNode!= null) {
removeNode(lruNode)
cache.remove(lruNode.key)
}
}
}
}
}A shorter LinkedHashMap version
LinkedHashMap already keeps a doubly linked list through its entries. One constructor orders that list by access instead of insertion.
With accessOrder set to true, a get moves that entry to the end of the internal list. That is the recency update.
Subclass LinkedHashMap and override removeEldestEntry(). When it returns true, the map drops the eldest entry. In access order, that entry is the least recently used.
The subclass does not manipulate node pointers itself.
import java.util.LinkedHashMap
class LRUCacheWithLinkedHashMap(private val capacity: Int) :
LinkedHashMap<Int, Int>(capacity, 0.75f, true) {
/**
* This method is invoked by put and putAll after inserting a new entry into the map.
* It provides the implementor with the opportunity to remove the eldest entry each time
* a new one is added. This is ideal for implementing a cache with a fixed capacity.
*
* @param eldest The least recently accessed entry in the map.
* @return true if the eldest entry should be removed, false otherwise.
*/
override fun removeEldestEntry(eldest: MutableMap.MutableEntry<Int, Int>?): Boolean {
return size > capacity
}
}
// The get and put methods are inherited from LinkedHashMap and work as required.
// No additional implementation is needed for the core LRU logic.The hand-built list shows the pointer updates. LinkedHashMap is the version that hides them.
Complexity
Both versions are O(1) average time and O(capacity) space.
Time complexity: O(1)
get(key): a hash map lookup is O(1) on average, and unlinking then relinking a node updates a fixed number of pointers, also O(1).put(key, value): lookup or insert is O(1) on average, creating a node is O(1), and the pointer updates that add a node at the head or remove one at the tail are O(1).
A hash collision can make a map operation O(n). With a normal hash function that is rare, and the bound people quote is amortised O(1).
Space complexity: O(capacity)
- The hash map stores
capacitykey-to-node references. - The doubly linked list stores up to
capacitynodes.
Both grow with capacity, so the space is O(capacity).
Where LRU shows up
The same map-plus-list shape shows up in operating-system page replacement, database buffer pools, and browser caches. Least Frequently Used (LFU) is the nearby variant: it counts how often a key is used, not only how recently.
Sources:
LeetCode clasifica este problema como Medium.
Para resolver el 146 de LeetCode con get y put en O(1), combinas un mapa hash con una lista doblemente enlazada: el mapa hash te da búsquedas en tiempo constante de la clave al nodo, y la lista enlazada mantiene los elementos ordenados por recencia, de modo que puedes desalojar el menos recientemente usado en tiempo constante. Más abajo muestro dos implementaciones en Kotlin: una desde cero, con una clase Node propia y centinelas ficticios de cabeza y cola, y otra más corta, que hereda de LinkedHashMap y sobreescribe removeEldestEntry. Las dos cumplen el requisito de tiempo medio O(1) y usan un espacio de O(capacity).
Por qué desaloja una caché LRU
Una caché tiene un tamaño fijo. Cuando está llena, una política de desalojo elige qué quitar. First-In-First-Out (FIFO) quita el elemento más antiguo. Least Recently Used (LRU) quita el elemento que lleva más tiempo sin usarse, por la localidad temporal: un dato usado hace poco tiene muchas probabilidades de volver a usarse pronto.
LeetCode 146 pide construir esa caché.
El problema
La clase tiene tres operaciones:
LRUCache(int capacity)inicializa la caché con un tamaño fijo y positivo. La capacidad es el número máximo de pares clave-valor.int get(int key)devuelve el valor dekey, o -1 si la clave no está. Un acierto marca la clave como usada recientemente.void put(int key, int value)inserta un par o actualiza uno que ya existe. En los dos casos, la clave pasa a ser la más reciente. Si una clave nueva superaría la capacidad, desaloja antes la clave menos recientemente usada.
get y put tienen que ejecutarse en tiempo medio O(1). El tiempo se mantiene constante, de media, aunque crezca la capacidad.
El ejemplo del enunciado usa una caché de capacidad 2:
| Operation | Action | Cache State (MRU -> LRU) | Output |
| :---------- | :----------------------------------------------------- | :----------------------- | :----- |
| `put(1, 1)` | Add {1:1}. Cache size is 1. | `{1:1}` | `null` |
| `put(2, 2)` | Add {2:2}. Cache size is 2. | `{2:2}, {1:1}` | `null` |
| `get(1)` | Access {1:1}. It becomes the most recently used (MRU). | `{1:1}, {2:2}` | `1` |
| `put(3, 3)` | Cache is full. Evict LRU item {2:2}. Add {3:3} as MRU. | `{3:3}, {1:1}` | `null` |
| `get(2)` | Key 2 was evicted and is no longer in the cache. | `{3:3}, {1:1}` | `-1` |
| `put(4, 4)` | Cache is full. Evict LRU item {1:1}. Add {4:4} as MRU. | `{4:4}, {3:3}` | `null` |Por qué no basta una sola estructura
El límite O(1) descarta usar solo un array, solo un mapa hash o solo una lista simplemente enlazada.
Un array o una lista
Un array o una lista pueden dejar el elemento más reciente en un extremo y el menos reciente en el otro. Encontrar una clave es un recorrido, O(n). Mover ese elemento al frente desplaza todos los que van por delante, también O(n).
Solo un mapa hash
Un mapa hash da búsqueda, inserción y borrado en tiempo medio O(1). No guarda orden. Encontrar la clave menos recientemente usada obliga a recorrer cada entrada, O(n).
Una lista simplemente enlazada
Insertar en la cabeza es O(1). Encontrar una clave es un recorrido desde la cabeza, O(n). El elemento menos recientemente usado está en la cola, y quitar la cola obliga a llegar al nodo anterior para actualizar next, también O(n).
Ninguna estructura, por sí sola, busca por clave en O(1) y reordena en O(1). La caché usa un mapa hash y una lista enlazada juntos.
El diseño
Junta un mapa hash con una lista doblemente enlazada.
El mapa hash: búsquedas en O(1)
El mapa guarda el nodo de cada clave, no el valor. get encuentra el nodo sin recorrer la lista.
La lista doblemente enlazada: orden en O(1)
El elemento más recientemente usado está en la cabeza. El menos recientemente usado está en la cola.
Cada nodo tiene next y prev. Cuando el mapa te da el nodo, lo desenlazas y lo mueves a la cabeza sin recorrer. El desalojo quita tail.prev.
Dos nodos ficticios, head y tail, no guardan datos de la caché. Cada nodo real queda entre ellos, así que un nodo que se añade o se quita siempre tiene vecinos.
Cada operación actualiza el mapa y la lista a la vez.
get y put
Las dos operaciones tocan el mapa y la lista.
get(key)
get lee un valor y mueve ese nodo al extremo más reciente.
- Comprueba si
keyestá en el mapa. - Si no está, devuelve
-1. - Si está, toma el
nodedel mapa, muévelo a la cabeza y devuelve elvalueguardado en el nodo. El movimiento desenlaza el nodo y luego lo inserta en la cabeza.
put(key, value)
put actualiza una clave que ya está guardada o inserta una que no lo está, y desaloja cuando la caché supera la capacidad.
- Comprueba si
keyestá en el mapa. - Si está, toma el
node, escribe elvaluenuevo y mueve el nodo a la cabeza. - Si no está, crea un nodo con esa clave y ese valor, inserta el nodo en la cabeza y asocia la clave al nodo.
- Si el tamaño supera ahora
capacity, el nodo menos recientemente usado es el que está justo antes del centinela de cola. Quita su clave del mapa y quita el nodo de la lista.
Después de cada operación, las claves del mapa son exactamente los nodos de la lista, del más reciente al menos reciente.
Una lista y un mapa en Kotlin
La primera versión usa un Node, un MutableMap y nodos ficticios de cabeza y cola.
Los centinelas no son nulos, así que la inserción y el borrado quedan siempre entre dos vecinos. No hay un caso aparte para la lista vacía.
class LRUCache(private val capacity: Int) {
// Inner class to represent a node in the doubly linked list
private class Node(
var key: Int,
var value: Int,
var prev: Node? = null,
var next: Node? = null
)
// The cache map for O(1) key-to-node lookup
private val cache: MutableMap<Int, Node> = HashMap()
// Dummy head and tail nodes to simplify list manipulation
private val head: Node = Node(-1, -1)
private val tail: Node = Node(-1, -1)
init {
// Initialize the doubly linked list with dummy nodes
head.next = tail
tail.prev = head
}
// Helper function to remove a node from the list
private fun removeNode(node: Node) {
val prevNode = node.prev
val nextNode = node.next
prevNode?.next = nextNode
nextNode?.prev = prevNode
}
// Helper function to add a node to the head of the list (MRU position)
private fun addToHead(node: Node) {
node.prev = head
node.next = head.next
head.next?.prev = node
head.next = node
}
fun get(key: Int): Int {
val node = cache[key]
if (node == null) {
// Key not found in cache
return -1
} else {
// Key found, move the node to the head to mark it as most recently used
removeNode(node)
addToHead(node)
return node.value
}
}
fun put(key: Int, value: Int) {
val node = cache[key]
if (node!= null) {
// Key already exists, update its value and move it to the head
node.value = value
removeNode(node)
addToHead(node)
} else {
// Key does not exist, create a new node
val newNode = Node(key, value)
cache[key] = newNode
addToHead(newNode)
// If adding the new node exceeds capacity, evict the LRU item
if (cache.size > capacity) {
val lruNode = tail.prev
if (lruNode!= null) {
removeNode(lruNode)
cache.remove(lruNode.key)
}
}
}
}
}Una versión más corta con LinkedHashMap
LinkedHashMap ya mantiene una lista doblemente enlazada a través de sus entradas. Un constructor ordena esa lista por acceso, en lugar de por inserción.
Con accessOrder a true, un get mueve esa entrada al final de la lista interna. Esa es la actualización de recencia.
Hereda de LinkedHashMap y sobreescribe removeEldestEntry(). Cuando devuelve true, el mapa quita la entrada más antigua. En orden de acceso, esa entrada es la menos recientemente usada.
La subclase no manipula punteros de nodos.
import java.util.LinkedHashMap
class LRUCacheWithLinkedHashMap(private val capacity: Int) :
LinkedHashMap<Int, Int>(capacity, 0.75f, true) {
/**
* This method is invoked by put and putAll after inserting a new entry into the map.
* It provides the implementor with the opportunity to remove the eldest entry each time
* a new one is added. This is ideal for implementing a cache with a fixed capacity.
*
* @param eldest The least recently accessed entry in the map.
* @return true if the eldest entry should be removed, false otherwise.
*/
override fun removeEldestEntry(eldest: MutableMap.MutableEntry<Int, Int>?): Boolean {
return size > capacity
}
}
// The get and put methods are inherited from LinkedHashMap and work as required.
// No additional implementation is needed for the core LRU logic.La lista hecha a mano muestra las actualizaciones de punteros. LinkedHashMap es la versión que las esconde.
Complejidad
Las dos versiones son tiempo medio O(1) y espacio O(capacity).
Complejidad temporal: O(1)
get(key): una búsqueda en el mapa hash es O(1) de media, y desenlazar y volver a enlazar un nodo actualiza un número fijo de punteros, también O(1).put(key, value): la búsqueda o la inserción es O(1) de media, crear un nodo es O(1), y las actualizaciones de punteros que añaden un nodo en la cabeza o quitan uno en la cola son O(1).
Una colisión de hash puede hacer que una operación del mapa sea O(n). Con una función de hash normal eso es raro, y la cota que se cita es O(1) amortizado.
Complejidad espacial: O(capacity)
- El mapa hash guarda
capacityreferencias de clave a nodo. - La lista doblemente enlazada guarda hasta
capacitynodos.
Las dos crecen con la capacidad, así que el espacio es O(capacity).
Dónde aparece LRU
La misma forma de mapa más lista aparece en el reemplazo de páginas de los sistemas operativos, en los buffer pools de las bases de datos y en las cachés de los navegadores. Least Frequently Used (LFU) es la variante cercana: cuenta cuántas veces se usa una clave, no solo cuán reciente es.
Loading comments…Cargando comentarios…