Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

LRU Cache

MEDIUMProblemSolveExternal Links

Description

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

An LRU cache is a fixed-size storage that keeps track of the order in which items are accessed. When the cache is full and a new item needs to be added, the item that was least recently used (accessed longest ago) is evicted to make room.

Implement the LRUCache class with the following operations:

  • LRUCache(int capacity) — Initialize the cache with a positive integer capacity.
  • int get(int key) — Return the value associated with the key if it exists in the cache. Otherwise, return -1. Accessing a key makes it the most recently used.
  • void put(int key, int value) — Insert or update the key-value pair. If the key already exists, update its value. If the cache is at capacity and the key is new, evict the least recently used key before inserting.

Both get and put must run in O(1) average time complexity.

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]

Explanation:

  • LRUCache(2) — Create cache with capacity 2.
  • put(1, 1) — Cache: {1=1}.
  • put(2, 2) — Cache: {1=1, 2=2}. Now full.
  • get(1) → returns 1. Key 1 becomes most recently used. Cache order: {2=2, 1=1}.
  • put(3, 3) — Cache is full. Key 2 is least recently used → evict it. Cache: {1=1, 3=3}.
  • get(2) → returns -1. Key 2 was evicted.
  • put(4, 4) — Cache full. Key 1 is LRU → evict. Cache: {3=3, 4=4}.
  • get(1) → returns -1. Key 1 was evicted.
  • get(3) → returns 3.
  • get(4) → returns 4.

Example 2

Input:

["LRUCache", "put", "put", "get", "get"]
[[1], [1, 10], [2, 20], [1], [2]]

Output: [null, null, null, -1, 20]

Explanation:

  • LRUCache(1) — Cache holds only 1 entry.
  • put(1, 10) — Cache: {1=10}.
  • put(2, 20) — Full! Only entry {1=10} is LRU → evict. Cache: {2=20}.
  • get(1) → -1 (evicted).
  • get(2) → 20.

Example 3

Input:

["LRUCache", "put", "put", "put", "get"]
[[2], [1, 1], [2, 2], [1, 10], [1]]

Output: [null, null, null, null, 10]

Explanation:

  • After put(1,1) and put(2,2), cache is {1=1, 2=2}.
  • put(1, 10) — Key 1 already exists. Update value to 10, no eviction needed. Key 1 becomes MRU.
  • get(1) → 10 (the updated value).

Constraints

  • 1 ≤ capacity ≤ 3000
  • 0 ≤ key ≤ 10^4
  • 0 ≤ value ≤ 10^5
  • At most 2 × 10^5 calls will be made to get and put

Editorial

Brute Force - Ordered Array with Linear Search

Intuition

The simplest way to implement an LRU cache is to maintain an ordered list (array) of key-value entries, where the position encodes recency: the front of the list holds the least recently used item, and the back holds the most recently used.

Imagine a stack of papers on your desk. Every time you use a document, you pull it out and place it on top. When you need space, you throw away the paper at the very bottom — the one you haven't touched in the longest time.

For get: scan the array to find the key. If found, remove it from its current position and append it to the end (marking it as most recently used). If not found, return -1.

For put: scan the array for the key. If it exists, remove and re-append with the new value. If it doesn't exist and the array is full, remove the first element (LRU) and then append the new entry.

Step-by-Step Explanation

Let's trace Example 1: capacity=2, operations: put(1,1), put(2,2), get(1), put(3,3), get(2), put(4,4), get(1), get(3), get(4).

Cache order: index 0 = LRU, last index = MRU.

Step 1: LRUCache(2). Create empty array. capacity=2.

Step 2: put(1,1). Scan for key 1 → not found. Not full (size=0 < 2). Append {1:1}.

  • Cache: [{1:1}]

Step 3: put(2,2). Scan for key 2 → not found. Not full. Append {2:2}.

  • Cache: [{1:1}, {2:2}]. Now full.

Step 4: get(1). Scan array: index 0 is {1:1} → key matches! Remove from index 0, append to end.

  • Cache: [{2:2}, {1:1}]. Return 1.

Step 5: put(3,3). Scan for key 3 → not found (checked both entries). Cache is full.

Step 6: Evict LRU (index 0 = {2:2}). Remove it, append {3:3}.

  • Cache: [{1:1}, {3:3}]

Step 7: get(2). Scan both entries: {1:1} has key 1 (≠2), {3:3} has key 3 (≠2). Not found. Return -1.

Step 8: put(4,4). Key 4 not found. Full. Evict LRU {1:1}. Append {4:4}.

  • Cache: [{3:3}, {4:4}]

Step 9: get(1). Scan: {3:3} key≠1, {4:4} key≠1. Not found. Return -1.

Step 10: get(3). Scan: index 0 is {3:3} → match! Remove, append to end.

  • Cache: [{4:4}, {3:3}]. Return 3.

Step 11: get(4). Scan: index 0 is {4:4} → match! Remove, append to end.

  • Cache: [{3:3}, {4:4}]. Return 4.

Notice: every get and put requires scanning the entire array. With capacity up to 3000 and 2×10^5 operations, that's up to 6×10^8 scans — far too slow.

Brute Force — Cache Operations with Linear Scanning — Watch how every get and put operation requires scanning the full array to find keys, making each operation O(n) where n is the cache capacity.

Algorithm

  1. Maintain an ordered array of key-value entries (index 0 = LRU, last = MRU)
  2. get(key):
    • Scan the array for the matching key
    • If found: remove from current position, append at end, return value
    • If not found: return -1
  3. put(key, value):
    • Scan the array for the key
    • If found: remove from current position, append with new value at end
    • If not found and cache is full: remove index 0 (LRU)
    • Append new {key: value} at end

Code

class LRUCache {
    int cap;
    vector<pair<int,int>> cache; // front = LRU, back = MRU
public:
    LRUCache(int capacity) : cap(capacity) {}

    int get(int key) {
        for (int i = 0; i < (int)cache.size(); i++) {
            if (cache[i].first == key) {
                int val = cache[i].second;
                cache.erase(cache.begin() + i);
                cache.push_back({key, val});
                return val;
            }
        }
        return -1;
    }

    void put(int key, int value) {
        for (int i = 0; i < (int)cache.size(); i++) {
            if (cache[i].first == key) {
                cache.erase(cache.begin() + i);
                cache.push_back({key, value});
                return;
            }
        }
        if ((int)cache.size() == cap) {
            cache.erase(cache.begin());
        }
        cache.push_back({key, value});
    }
};
class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache = []  # list of [key, value], front=LRU, back=MRU

    def get(self, key: int) -> int:
        for i in range(len(self.cache)):
            if self.cache[i][0] == key:
                val = self.cache[i][1]
                self.cache.pop(i)
                self.cache.append([key, val])
                return val
        return -1

    def put(self, key: int, value: int) -> None:
        for i in range(len(self.cache)):
            if self.cache[i][0] == key:
                self.cache.pop(i)
                self.cache.append([key, value])
                return
        if len(self.cache) == self.cap:
            self.cache.pop(0)
        self.cache.append([key, value])
class LRUCache {
    private int cap;
    private List<int[]> cache;

    public LRUCache(int capacity) {
        cap = capacity;
        cache = new ArrayList<>();
    }

    public int get(int key) {
        for (int i = 0; i < cache.size(); i++) {
            if (cache.get(i)[0] == key) {
                int val = cache.get(i)[1];
                cache.remove(i);
                cache.add(new int[]{key, val});
                return val;
            }
        }
        return -1;
    }

    public void put(int key, int value) {
        for (int i = 0; i < cache.size(); i++) {
            if (cache.get(i)[0] == key) {
                cache.remove(i);
                cache.add(new int[]{key, value});
                return;
            }
        }
        if (cache.size() == cap) {
            cache.remove(0);
        }
        cache.add(new int[]{key, value});
    }
}

Complexity Analysis

Time Complexity: O(n) per operation, where n = capacity

Both get and put require scanning the entire array to find (or confirm absence of) a key. Additionally, removing an element from the middle or front of an array requires shifting all subsequent elements, which is also O(n). With up to 2×10^5 calls and capacity up to 3000, worst-case total work is 6×10^8 — too slow.

Space Complexity: O(n)

The array stores at most capacity entries, each containing a key-value pair.

Why This Approach Is Not Efficient

The brute force takes O(n) per operation where n is the cache capacity. The problem explicitly requires O(1) average time for both get and put. With capacity up to 3000 and 2×10^5 calls, O(n) per call gives up to 6×10^8 operations — well beyond typical time limits.

The bottleneck has two parts:

  1. Key lookup is O(n) — we scan the entire array to find a key. A hash map can provide O(1) lookup.
  2. Reordering is O(n) — moving an element from the middle to the end requires shifting array elements. A linked list can provide O(1) insertion and deletion anywhere, if we have a direct pointer to the node.

The key insight: by combining a hash map with a doubly linked list, we get O(1) for both key lookup (via the hash map) and order maintenance (via the linked list). The hash map stores key → linked list node pointers, giving us instant access to any node. The doubly linked list lets us remove any node and insert at the head in O(1) — no shifting needed.

Optimal Approach - Hash Map + Doubly Linked List

Intuition

Think of a VIP club with a velvet rope line. People stand in a queue — the person at the front of the line has been waiting the longest (least recently active), and the person at the back just arrived (most recently active).

The doubly linked list is the rope line — it maintains the access order. The most recently used item is at the head (front of list), and the least recently used is at the tail (back of list).

The hash map is the bouncer's guest list — given any person's name (key), the bouncer instantly knows where they are in the line (direct node pointer). Without the guest list, the bouncer would have to walk the entire line to find someone — that's the O(n) brute force.

With both structures working together:

  • get(key): The bouncer checks the guest list (hash map lookup, O(1)). If found, the person is pulled from their current position in line (doubly linked list removal, O(1)) and placed at the front (insertion at head, O(1)).
  • put(key, value): If the person is already in line, update and move to front. If new and the line is full, the person at the very back (tail = LRU) is asked to leave, and the new person enters at the front.

We use sentinel nodes (dummy head and tail) to simplify edge cases — we never need to handle null pointers when the list is empty or has one element.

Step-by-Step Explanation

Let's trace Example 1 with the doubly linked list. We show the list from head (MRU) to tail (LRU).

Step 1: LRUCache(2). Initialize: dummy head ↔ dummy tail, empty hash map.

Step 2: put(1,1). Key 1 not in map. Not full. Create node, add after head.

  • List: [1:1] | Map: {1→node}

Step 3: put(2,2). Key 2 not in map. Add at head.

  • List: [2:2 ↔ 1:1] | Map: {1→node, 2→node}. Full.

Step 4: get(1). Hash map lookup: key 1 → found! Node is at tail position.

Step 5: Move node {1:1} to head.

  • List: [1:1 ↔ 2:2]. Return 1.

Step 6: put(3,3). Key 3 not in map. Cache full. Identify LRU at tail: {2:2}.

Step 7: Remove tail node {2:2} from list and map.

  • List: [1:1]

Step 8: Add node {3:3} at head.

  • List: [3:3 ↔ 1:1] | Map: {1→node, 3→node}

Step 9: get(2). Hash map lookup: key 2 → NOT FOUND (evicted). Return -1.

Step 10: put(4,4). Key 4 not in map. Full. Evict tail {1:1}. Add {4:4} at head.

  • List: [4:4 ↔ 3:3] | Map: {3→node, 4→node}

Step 11: get(1). Key 1 not in map (evicted). Return -1.

Step 12: get(3). Found in map. Move to head.

  • List: [3:3 ↔ 4:4]. Return 3.

Step 13: get(4). Found in map. Move to head.

  • List: [4:4 ↔ 3:3]. Return 4.

Every operation — lookup, move, evict, insert — was O(1). No scanning needed.

Optimal — Hash Map + Doubly Linked List Operations — Watch how the doubly linked list maintains access order while the hash map provides instant key lookup. Every operation is O(1) — no scanning, no shifting.

Algorithm

Data Structures:

  • Doubly linked list with sentinel head (MRU end) and sentinel tail (LRU end)
  • Hash map: key → pointer to the linked list node

Helper operations (all O(1)):

  • remove(node): Unlink a node from the list by rewiring its prev and next pointers
  • addToHead(node): Insert a node right after the sentinel head

LRUCache(capacity):

  1. Store capacity. Create sentinel head and tail, link them together. Create empty hash map.

get(key):

  1. If key not in map → return -1
  2. Get node from map
  3. remove(node) then addToHead(node) (move to MRU position)
  4. Return node.value

put(key, value):

  1. If key in map → remove the existing node, delete from map
  2. If map size == capacity → remove the node before sentinel tail (LRU), delete its key from map
  3. Create new node with key and value
  4. addToHead(newNode), store in map

Code

class LRUCache {
    struct Node {
        int key, val;
        Node* prev;
        Node* next;
        Node(int k, int v) : key(k), val(v), prev(nullptr), next(nullptr) {}
    };

    int cap;
    unordered_map<int, Node*> mp;
    Node* head; // sentinel head (MRU side)
    Node* tail; // sentinel tail (LRU side)

    void remove(Node* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    void addToHead(Node* node) {
        node->next = head->next;
        node->prev = head;
        head->next->prev = node;
        head->next = node;
    }

public:
    LRUCache(int capacity) : cap(capacity) {
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head->next = tail;
        tail->prev = head;
    }

    int get(int key) {
        if (mp.find(key) == mp.end()) return -1;
        Node* node = mp[key];
        remove(node);
        addToHead(node);
        return node->val;
    }

    void put(int key, int value) {
        if (mp.find(key) != mp.end()) {
            remove(mp[key]);
            delete mp[key];
            mp.erase(key);
        }
        if ((int)mp.size() == cap) {
            Node* lru = tail->prev;
            remove(lru);
            mp.erase(lru->key);
            delete lru;
        }
        Node* node = new Node(key, value);
        addToHead(node);
        mp[key] = node;
    }
};
class Node:
    def __init__(self, key: int = 0, val: int = 0):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.mp = {}  # key -> Node
        self.head = Node()  # sentinel head (MRU side)
        self.tail = Node()  # sentinel tail (LRU side)
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node: Node) -> None:
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_to_head(self, node: Node) -> None:
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:
        if key not in self.mp:
            return -1
        node = self.mp[key]
        self._remove(node)
        self._add_to_head(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        if key in self.mp:
            self._remove(self.mp[key])
            del self.mp[key]
        if len(self.mp) == self.cap:
            lru = self.tail.prev
            self._remove(lru)
            del self.mp[lru.key]
        node = Node(key, value)
        self._add_to_head(node)
        self.mp[key] = node
class LRUCache {
    class Node {
        int key, val;
        Node prev, next;
        Node(int k, int v) { key = k; val = v; }
    }

    private int cap;
    private Map<Integer, Node> map;
    private Node head, tail; // sentinels

    public LRUCache(int capacity) {
        cap = capacity;
        map = new HashMap<>();
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
    }

    private void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void addToHead(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }

    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        Node node = map.get(key);
        remove(node);
        addToHead(node);
        return node.val;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            remove(map.get(key));
            map.remove(key);
        }
        if (map.size() == cap) {
            Node lru = tail.prev;
            remove(lru);
            map.remove(lru.key);
        }
        Node node = new Node(key, value);
        addToHead(node);
        map.put(key, node);
    }
}

Complexity Analysis

Time Complexity: O(1) per operation (amortized)

  • get: One hash map lookup (O(1)), one linked list removal (O(1) — just rewire 4 pointers), one insertion at head (O(1) — rewire 4 pointers). Total: O(1).
  • put: One hash map lookup (O(1)), at most one removal + one eviction + one insertion — each O(1). Total: O(1).

With 2×10^5 calls, total work is 2×10^5 × O(1) = O(2×10^5) — well within time limits.

Space Complexity: O(capacity)

The hash map stores at most capacity entries (key → node pointer). The doubly linked list has at most capacity data nodes plus 2 sentinel nodes. Total: O(capacity) = O(3000) at most.