LRUCache using stack is not efficient enough

Question

I am trying to solve the LeetCode problem 146. LRU Cache:

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

Implement the LRUCache class:

• LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
• int get(int key) Return the value of the key if the key exists, otherwise return -1.
• void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.

This is my code:

class LRUCache {
    Stack<Integer> stack;
    HashMap<Integer, Integer> cache;
    int capacity;
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        stack = new Stack<>();
        cache = new HashMap<>();        
    }
    
    public int get(int key) {
        if(!cache.containsKey(key)) return -1;
        else 
            stack.removeElement(key);
            stack.push(key);
            return cache.get(key);
    }
    
    public void put(int key, int value) {
        if(cache.containsKey(key)){
            stack.removeElement(key);
        }
        else if(stack.size() == capacity){
            int leastRecent = stack.remove(0);
            cache.remove(leastRecent);
        }
        stack.push(key);
        cache.put(key, value);
    }
}

/*
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

All the test cases passed but I am getting "time limit exceeded" error:

How can I improve the efficiency of my code?

Answer 1

The time out occurs because stack.removeElement(key) does not have a good enough time complexity, and thus -- for some tests with bigger entry sets -- you'll get a time out.

The code challenge on LeetCode gives this information:

The functions get and put must each run in O(1) average time complexity.

So that really means you cannot use stack.removeElement or anything that similarly has O() time complexity. It must be done more efficiently.

If you want to do this with your HashMap then you would need to have a doubly linked list, and then have the hashmap reference the node in that doubly linked list. That way you can remove a node in constant time.

But,... Java has all this done for you with LinkedHashMap! The documentation explains:

A special constructor is provided to create a linked hash map whose order of iteration is the order in which its entries were last accessed, from least-recently accessed to most-recently (access-order). This kind of map is well-suited to building LRU caches.

So then the code becomes quite simple:

class LRUCache extends LinkedHashMap<Integer, Integer> {
    int capacity;  
    
    public LRUCache(int capacity) {
        // Foresee one more than desired capacity, so no extension is needed
        // when we allow a temporary overrun before deleting the eldest entry
        super(capacity + 1, 1, true); // true will enable the LRU behavior
        this.capacity = capacity;
    }

    // This method is called internally by put, getOrDefault (and similar).
    //    See documentation
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> entry) {
        return this.size() > this.capacity; // overrun detected: ask for removal
    }
    
    public int get(int key) {
        return getOrDefault(key, -1);
    }
}