LeetCode 146: LRU Cache Solution

Master LeetCode problem 146 (LRU Cache), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

146. LRU Cache

Medium

Hash Table Linked List Design Doubly-Linked List

Problem Explanation

Explanation

To implement an LRU cache, we can use a combination of a hashmap and a doubly linked list. The hashmap is used to quickly access the nodes in the linked list by their keys, while the linked list maintains the order of recently used keys.

Algorithm:

Initialize a hashmap to store key-value pairs and a doubly linked list to maintain the order of recently used keys.
For get operation:
- If the key exists in the hashmap:
  - Move the node corresponding to the key to the front of the linked list (indicating it as the most recently used).
  - Return the value.
  - If the key doesn't exist, return -1.
For put operation:
- If the key already exists, update the value and move the corresponding node to the front.
- If the key doesn't exist:
  - Create a new node with the key-value pair.
  - Add this node to the front of the linked list.
  - If the size exceeds the capacity, remove the least recently used node from the end of the linked list and the hashmap.

Time Complexity:

Both get and put operations will run in O(1) time complexity on average.

Space Complexity:

O(capacity) for the hashmap and doubly linked list.

Solution Code

class LRUCache {
    class Node {
        int key;
        int value;
        Node prev;
        Node next;
        
        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    
    private int capacity;
    private Map<Integer, Node> cache;
    private Node head;
    private Node tail;
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        cache = new HashMap<>();
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
    }
    
    public int get(int key) {
        if (cache.containsKey(key)) {
            Node node = cache.get(key);
            remove(node);
            addToFront(node);
            return node.value;
        }
        return -1;
    }
    
    public void put(int key, int value) {
        if (cache.containsKey(key)) {
            Node node = cache.get(key);
            node.value = value;
            remove(node);
            addToFront(node);
        } else {
            if (cache.size() == capacity) {
                cache.remove(tail.prev.key);
                remove(tail.prev);
            }
            Node newNode = new Node(key, value);
            cache.put(key, newNode);
            addToFront(newNode);
        }
    }
    
    private void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    
    private void addToFront(Node node) {
        Node headNext = head.next;
        head.next = node;
        node.prev = head;
        node.next = headNext;
        headNext.prev = node;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 146 (LRU Cache)?

This page provides optimized solutions for LeetCode problem 146 (LRU Cache) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 146 (LRU Cache)?

The time complexity for LeetCode 146 (LRU Cache) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 146 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 146 in Java, C++, or Python.

Back to LeetCode Solutions