LRU Cache

Time: O(1)

Space: O(capacity)

Problem Overview

Same as LeetCode 146: HashMap + doubly linked list.

Intuition

Same as LeetCode 146: HashMap + doubly linked list. O(1) get and put. HashMap maps key to node; DLL maintains recency order.

Algorithm

1Create dummy head and tail nodes. Connect them. Map starts empty.
2get(key): if not in map, return -1. Otherwise move the node to just after the dummy head and return its value.
3put(key, value): if key exists, update value and move to front. If new: insert new node at front.
4After inserting a new node: if size > capacity, remove the node just before the dummy tail (LRU) and delete its key from the map.
5Helper Remove(node) unlinks a node in O(1). Helper InsertFront(node) inserts after head in O(1).

Example Walkthrough

Input: capacity=2, put(1,1),put(2,2),get(1),put(3,3),get(2)

1. get(1)=1. After put(3): evicts key 2. get(2)=-1.

Output: get(1)=1, get(2)=-1

Common Pitfalls

• Evict the LEAST recently used (tail node), not the least frequently used.

LRU Cache.java

Java

// Approach: HashMap + Doubly Linked List. HashMap for O(1) access; DLL for O(1) move-to-front and eviction.
// Time: O(1) Space: O(capacity)
class LRUCache {
    private static int capacity;
    private static LinkedHashMap<Integer, Integer> cache;

    // Constructor for initializing the cache capacity with the given value.
    LRUCache(int cap) {
        capacity = cap;
        cache = new LinkedHashMap<>(cap, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
                return size() > capacity;
            }
        };
    }

    // Function to return value corresponding to the key.
    public static int get(int key) {
        return cache.getOrDefault(key, -1);
    }

    // Function for storing key-value pair.
    public static void put(int key, int value) {
        cache.put(key, value);
    }
}

Was this solution helpful?