LRU Cache Editorial

Practice Problem Link: LRU Cache

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Implement Least Recently Used (LRU) cache.

You need to implement the following for the LRUCache class:

• LRUCache(int capacity) initializes the cache to store data of size: capacity.
• int get(int key) returns the value of the key if it exists, otherwise returns -1.
• void add(int key, int value) updates 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.

Note: Try to achieve each operation in O(1) time complexity.

Approach

The idea is to create a doubly linked list to store the key-value in the order in which they are used. To add a new key-value pair simply just add it in the front and make it the head node. Also, store the nodes in a hashmap so that updating and using a key can be done in constant time. After updating or getting a key remove it from its current position in the linked list and make it the new head of the linked list. Refer to the implementation for better understanding.

Analysis

• Time Complexity: O(1)
• Space Complexity: O(Max Capacity)

Implementation

C++

class Node {
public:
	int value;
	int key;
	Node* next;
	Node* prev;
	
    Node(int key, int value) {
		this->key = key;
		this->value = value;
	}
};
class LRUCache {
	Node* head = NULL;
    Node* tail = NULL;
    unordered_map<int, Node*> keyToNode;
    int capacity;
	
	void moveToHead(Node* n) {
        if (head == n) {
            return;
        }
        Node* prev = n->prev;
        Node* next = n->next;
        if (n == tail) {
            tail = prev;
        }
        prev->next = n->next;
        if (next != NULL) {
            next->prev = prev;
        }
		
        n->prev = NULL;
        n->next = head;
        head->prev = n;
        head = n;
    }
	
public:
    LRUCache(int capacity) {
		keyToNode.clear();
        this->capacity = capacity;
    }
    
    int get(int key) {
		if (keyToNode.find(key) == keyToNode.end()) {
            return -1;
        }
        Node* n = keyToNode[key];        
        moveToHead(n);
        return head->value;
    }    
	
    void add(int key, int value) {
		if (keyToNode.find(key) != keyToNode.end()) {
            Node* n = keyToNode[key];
            n->value = value;      
            moveToHead(n);
        } else {
            if (keyToNode.size() == capacity) {
                Node* last = tail;
                tail = tail->prev;
                
                if (tail != NULL) {
                    tail->next = NULL;
                } else {
                    head = NULL;
                }
                keyToNode.erase(last->key);
            }
            Node* n = new Node(key, value);
            if (head == NULL) {
                tail = n;
            } else {
                n->next = head;
                head->prev = n; 
            }
            head = n;
            keyToNode[key] = n;
        }
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* cache = new LRUCache(capacity);
 * int value = cache->get(key);
 * cache->add(key, value);
 */

Java

class Node {
	int value;
	int key;
	Node next;
	Node prev;

	public Node(int key, int value) {
		this.key = key;
		this.value = value;
	}
}

class LRUCache {
    private Node head;
    private Node tail;
    private Map<Integer, Node> keyToNode;
    private int capacity;
	
    public LRUCache(int capacity) {
        this.keyToNode = new HashMap<>();
        this.capacity = capacity;
    }
    
    public int get(int key) {
        if (!keyToNode.containsKey(key)) {
            return -1;
        }
        Node n = keyToNode.get(key);        
        moveToHead(n);
        return head.value;
    }
    
    private void moveToHead(Node n) {
        if (head == n) {
            return;
        }
        Node prev = n.prev;
        Node next = n.next;
        if (n == tail) {
            tail = prev;
        }
  
        prev.next = n.next;
        if (next != null) {
            next.prev = prev;
        }
		
        n.prev = null;
        n.next = head;
        head.prev = n;
        head = n;
    }
	
    public void add(int key, int value) {
        if (keyToNode.containsKey(key)) {
            Node n = keyToNode.get(key);
            n.value = value;      
            moveToHead(n);
        } else {
            if (keyToNode.size() == capacity) {
                Node last = tail;
                tail = tail.prev;
                
                if (tail != null) {
                    tail.next = null;
                } else {
                    head = null;
                }
                keyToNode.remove(last.key);
            }
            Node n = new Node(key, value);
            if (head == null) {
                tail = n;
            } else {
                n.next = head;
                head.prev = n; 
            }
            head = n;
            keyToNode.put(key, n);
        }
    }
}

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