LRU Cache
Solve this ProblemTest Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ capacity ≤ 5 - ◆
1 ≤ number of operations ≤ 10 - ◆
Each operation is "get" or "put" - ◆
0 ≤ key, value ≤ 200 - ◆
This version replays a fixed sequence of operations and reports the result of every get call, in order (put has no return value in the real API, so only get results are collected)
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Array of Pairs, Move-to-Front
GoodKeep the cache as a plain list of [key, value] pairs ordered from most to least recently used. For get, scan the list for the key; if found, pull it out and reinsert it at the front, returning its value (or -1 if missing). For put, scan for the key first — update and move it to the front if it exists; otherwise, evict the last (least recently used) pair if the cache is full, then insert the new pair at the front. Every operation is correct, but scanning and shifting the list makes each one O(capacity) instead of O(1).
O(n) per operationO(capacity)1class Solution {
2 public int[] lruCacheGetResults(int capacity, String[] ops, int[][] args) {
3 List<int[]> cache = new ArrayList<>();
4 List<Integer> results = new ArrayList<>();
5 for (int i = 0; i < ops.length; i++) {
6 int key = args[i][0];
7 if (ops[i].equals("get")) {
8 int foundAt = -1;
9 for (int m = 0; m < cache.size(); m++) {
10 if (cache.get(m)[0] == key) { foundAt = m; break; }
11 }
12 if (foundAt == -1) {
13 results.add(-1);
14 } else {
15 int[] pair = cache.remove(foundAt);
16 cache.add(0, pair);
17 results.add(pair[1]);
18 }
19 } else {
20 int value = args[i][1];
21 int foundAt = -1;
22 for (int m = 0; m < cache.size(); m++) {
23 if (cache.get(m)[0] == key) { foundAt = m; break; }
24 }
25 if (foundAt != -1) {
26 cache.remove(foundAt);
27 } else if (cache.size() == capacity) {
28 cache.remove(cache.size() - 1);
29 }
30 cache.add(0, new int[]{key, value});
31 }
32 }
33 int[] output = new int[results.size()];
34 for (int i = 0; i < results.size(); i++) output[i] = results.get(i);
35 return output;
36 }
37}Optimal — HashMap + Doubly Linked List
OptimalTrack the cache with two structures working together: a hash map from key to its position, and a doubly linked list ordered from most to least recently used, so both "find a key" and "move a key to the front" become O(1) instead of a scan. On get, jump straight to the key's node via the map, unlink it, and relink it at the front. On put, do the same if the key exists (also updating its value); otherwise evict the tail (least recently used) node when full, then insert a fresh node at the front and record it in the map. No operation ever needs to walk the structure.
O(1) per operationO(capacity)1class Solution {
2 public int[] lruCacheGetResults(int capacity, String[] ops, int[][] args) {
3 LinkedHashMap<Integer, Integer> cache = new LinkedHashMap<>(capacity, 0.75f, true) {
4 protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
5 return size() > capacity;
6 }
7 };
8 List<Integer> results = new ArrayList<>();
9 for (int i = 0; i < ops.length; i++) {
10 if (ops[i].equals("get")) {
11 int key = args[i][0];
12 Integer val = cache.get(key);
13 results.add(val == null ? -1 : val);
14 } else {
15 int key = args[i][0];
16 int value = args[i][1];
17 cache.put(key, value);
18 }
19 }
20 int[] output = new int[results.size()];
21 for (int i = 0; i < results.size(); i++) output[i] = results.get(i);
22 return output;
23 }
24}