Difficulty: MediumLinked List

LRU Cache

Problem in Plain English

Design a fixed-capacity cache that returns stored values by key and evicts the least recently used entry when full. Both reads and writes must run in constant average time.

Problem Statement

Build a cache with a positive entry limit capacity. LRUCache(capacity) creates an empty cache. get(key) returns the stored value, or -1 if the key is missing. put(key, value) replaces an existing value or adds a new entry. When a new entry would exceed the limit, remove the key used least recently.

A successful get, an update, and a new insertion all make that key most recently used; a failed get changes nothing. Both methods must take $O(1)$ average time. In the operation-sequence output, the constructor and put produce null, while get produces its returned integer.

Constraints

$1 \leq capacity \leq 3000$ .
$0 \leq key \leq 10^4$ .
$0 \leq value \leq 10^5$ .
At most $2 \times 10^5$ calls are made to get and put.

Examples

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]

With capacity 2, get(1) returns 1, put(3, 3) evicts key 2, and put(4, 4) evicts key 1, leaving values 3 and 4.

Example 2

Input: ["LRUCache", "get", "put", "put", "get", "put", "get", "get"] [[1], [0], [0, 0], [0, 100000], [0], [10000, 7], [0], [10000]]
Output: [null, -1, null, null, 100000, null, -1, 7]

With capacity 1, the empty read misses. Writing key 0 twice updates its value without evicting it or adding another entry; its value becomes 100000. Inserting key 10000 then evicts 0, so the final reads return -1 and 7. Zero is a valid key and value.

Example 3

Input: ["LRUCache", "put", "put", "put", "get", "put", "get", "get", "get", "put", "get"] [[2], [1, 10], [2, 20], [1, 11], [9], [3, 30], [2], [1], [3], [2, 22], [1]]
Output: [null, null, null, null, -1, null, -1, 11, 30, null, -1]

Updating key 1 refreshes it, making 2 oldest. The miss on 9 changes nothing, so adding 3 evicts 2. Reading 1 then 3 makes 1 oldest again. Reinserting previously evicted key 2 creates a fresh entry with value 22 and evicts 1.

Intuition

A cache needs both a key-to-value lookup and a memory of which entry was touched last. Least recently used means the entry whose latest successful get or put happened earliest. In Example 1, reading key 1 moves it ahead of key 2, so inserting key 3 must evict 2 even though 1 was inserted first. A miss has no stored entry to refresh. A map supplies lookup, while a doubly linked list supplies recency: each node has links to both neighbors, so a known node can be removed and moved without scanning.

Approaches

Array List Scan

Solution Details

Reveal Array List Scan: intuition, complexity, and code

Intuition

Keep unique key-value pairs in an array ordered from oldest to newest use. A successful lookup removes its pair and appends it; inserting a missing key discards the first pair when full. This makes the eviction rule visible, but searching and shifting the array each cost linear time, so this baseline fails the required average constant-time methods.

Step-by-Step Logic

Initialize an empty list and retain the positive capacity. Example 1 begins with capacity 2 and [].
For get, scan pairs from the front. On a hit remove that pair, append it at the back, and return its value; on a miss return -1 without a mutation. After inserting 1 and 2, get(1) changes [(1,1),(2,2)] to [(2,2),(1,1)].
For put, scan for the key first. An existing key is removed and appended with its new value, so an update refreshes recency without eviction or growth.
When a put has no match, remove the front only if the list is already full, then append the new pair. Example 1 evicts 2 for 3, then evicts 1 for 4.
Continue using the same rules for every call. The misses on 2 and 1 leave the list unchanged; the final reads of 3 and 4 return 3 and 4 while moving each to the back.

Why It Works

Initially the list is empty and satisfies uniqueness, current values, and oldest-to-newest order. A successful get removes exactly the matching pair and appends it, preserving all values and the relative order of every other key while making the accessed key newest. A put on an existing key does the same with the replacement value and cannot increase the size. A missing get changes nothing. For a new put, if full, the front is exactly the least recently used key by the invariant; removing it and appending the new pair restores the size limit and ordering. Induction over calls proves every returned value and eviction is correct.

Dry Run

Array List Scan: variable states at each step
Call / internal action	Search and movement	List oldest to newest	Size / capacity	Output so far
Constructor	no scan	[]	0 / 2	[null]
put(1,1)	empty scan; append (1,1)	[(1,1)]	1 / 2	[null,null]
put(2,2)	i=0: key 1 differs; append (2,2)	[(1,1),(2,2)]	2 / 2	[null,null,null]
get(1): remove	i=0: hit; save (1,1), shift (2,2) left	[(2,2)]	1 / 2	unchanged
get(1): append / return	append saved pair	[(2,2),(1,1)]	2 / 2	[null,null,null,1]
put(3,3): scan / evict	i=0 key 2, i=1 key 1 both differ; remove front (2,2)	[(1,1)]	1 / 2	unchanged
put(3,3): append	append (3,3)	[(1,1),(3,3)]	2 / 2	[null,null,null,1,null]
get(2)	i=0 key 1, i=1 key 3 both differ; no mutation	[(1,1),(3,3)]	2 / 2	[null,null,null,1,null,-1]
put(4,4): scan / evict	i=0 key 1, i=1 key 3 both differ; remove front (1,1)	[(3,3)]	1 / 2	unchanged
put(4,4): append	append (4,4)	[(3,3),(4,4)]	2 / 2	[null,null,null,1,null,-1,null]
get(1)	i=0 key 3, i=1 key 4 both differ; no mutation	[(3,3),(4,4)]	2 / 2	[null,null,null,1,null,-1,null,-1]
get(3): remove	i=0: hit; save (3,3), shift (4,4) left	[(4,4)]	1 / 2	unchanged
get(3): append / return	append saved pair	[(4,4),(3,3)]	2 / 2	[null,null,null,1,null,-1,null,-1,3]
get(4): remove	i=0: hit; save (4,4), shift (3,3) left	[(3,3)]	1 / 2	unchanged
get(4): append / return	append saved pair	[(3,3),(4,4)]	2 / 2	[null,null,null,1,null,-1,null,-1,3,4]

Complexity Analysis

Time Complexity

O(C)

Space Complexity

O(C)

Let C be capacity and q the number of calls. Each get and put takes O(C) worst-case time: a miss scans up to C pairs, while a hit or eviction may shift O(C) array entries. Appending is amortized O(1) in the usual dynamic-array model, with O(C) occasional resizing, which does not change this bound. A worst-case sequence costs O(qC); capacity 1 specializes to O(1) per call. Construction takes O(1) and initially constant space. The array retains at most C pairs and O(C) backing storage; per-call temporary state is O(1), and outputs are excluded. This method is correct but fails the required average O(1) bound as C grows.

Code

Solution.java

1import java.util.List;2import java.util.ArrayList;3
4class LRUCache {5    private int capacity;6    private List<int[]> cache;7
8    public LRUCache(int capacity) {9        this.capacity = capacity;10        this.cache = new ArrayList<>();11    }12
13    public int get(int key) {14        for (int i = 0; i < cache.size(); i++) {15            if (cache.get(i)[0] == key) {16                int[] entry = cache.remove(i);17                cache.add(entry);18                return entry[1];19            }20        }21        return -1;22    }23
24    public void put(int key, int value) {25        for (int i = 0; i < cache.size(); i++) {26            if (cache.get(i)[0] == key) {27                cache.remove(i);28                cache.add(new int[] { key, value });29                return;30            }31        }32        if (cache.size() == capacity) {33            cache.remove(0);34        }35        cache.add(new int[] { key, value });36    }37}

Hints

Hint 1

Think of recency as an ordering of distinct keys. Which end should lose an entry, and which operations should move an entry to the other end?

Hint 2

An array can represent that order, but finding and removing an interior entry costs linear time. How can you retain a direct reference to the entry?

Hint 3

Map each key to a doubly linked node. Use two guards, refresh successful accesses at the head, and remove the node before the tail when over capacity.

Edge Cases

Capacity 1: an update keeps the sole key, but inserting a distinct key evicts it; the same guard rewiring handles both.
Getting from an empty cache or requesting an evicted key returns -1 without changing recency.
A successful get must refresh even when it returns value 0; use key presence rather than value truthiness.
Updating the least recent key changes its value and makes it newest without evicting another key.
Repeated gets of the already newest node still work: detach first and reinsert, avoiding self-links.
Reinserting an evicted key creates a fresh entry, and every insertion keeps the map and list synchronized.

Common Mistakes and Interview Tips

Treating insertion order as usage order: get(1) in Example 1 must protect key 1 and make key 2 the next victim.
Evicting on every put when full, even if the key already exists. An update does not grow the number of entries.
Removing a node from the list but leaving its map entry allows a later get to resurrect an evicted key.
Storing only values in nodes leaves eviction unable to identify the map key to delete.
Reassigning head.next before saving the old neighbor, or fixing only one neighbor link, can corrupt the list. Detach and insert must maintain both directions.
Failing to refresh successful gets or updates, or refreshing a miss, changes which key the next insertion evicts.
Calling hash-map operations worst-case constant time ignores collisions and resizing; the required bound is average, with an amortized insertion qualification.

Key Takeaway

When ordering and lookup must both be instant, map keys to doubly linked nodes so each structure covers the weakness of the other.