146. LRU Cache - DevCodeEx

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.

View Leetcode Problem

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;
    }
}

Code Editor (Testing phase)

Improve Your Solution

Use the editor below to refine the provided solution. Select a programming language and try the following:

Add import statement if required.
Optimize the code for better time or space complexity.
Add test cases to validate edge cases and common scenarios.
Handle error conditions or invalid inputs gracefully.
Experiment with alternative approaches to deepen your understanding.

Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.

Sign in to devexcode.com with google.com

Explanation

Code Editor (Testing phase)

Improve Your Solution