146. LRU Cache

Approach 1: Node w/ prev and next pointers

• Time: get(key: int),, put(key: int, value: int): $O(1)$
• Space: $O(\texttt{capacity})$

C++JavaPython

struct Node {
  int key;
  int value;
  shared_ptr<Node> prev;
  shared_ptr<Node> next;
};

class LRUCache {
 public:
  LRUCache(int capacity) : capacity(capacity) {
    join(head, tail);
  }

  int get(int key) {
    const auto it = keyToNode.find(key);
    if (it == keyToNode.cend())
      return -1;

    shared_ptr<Node> node = it->second;
    remove(node);
    moveToHead(node);
    return node->value;
  }

  void put(int key, int value) {
    if (const auto it = keyToNode.find(key); it != keyToNode.cend()) {
      shared_ptr<Node> node = it->second;
      node->value = value;
      remove(node);
      moveToHead(node);
      return;
    }

    if (keyToNode.size() == capacity) {
      shared_ptr<Node> lastNode = tail->prev;
      keyToNode.erase(lastNode->key);
      remove(lastNode);
    }

    moveToHead(make_shared<Node>(key, value));
    keyToNode[key] = head->next;
  }

 private:
  const int capacity;
  unordered_map<int, shared_ptr<Node>> keyToNode;
  shared_ptr<Node> head = make_shared<Node>(-1, -1);
  shared_ptr<Node> tail = make_shared<Node>(-1, -1);

  void join(shared_ptr<Node> node1, shared_ptr<Node> node2) {
    node1->next = node2;
    node2->prev = node1;
  }

  void moveToHead(shared_ptr<Node> node) {
    join(node, head->next);
    join(head, node);
  }

  void remove(shared_ptr<Node> node) {
    join(node->prev, node->next);
  }
};

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

class LRUCache {
  public LRUCache(int capacity) {
    this.capacity = capacity;
  }

  public int get(int key) {
    if (!keyToNode.containsKey(key))
      return -1;

    Node node = keyToNode.get(key);
    cache.remove(node);
    cache.add(node);
    return node.value;
  }

  public void put(int key, int value) {
    if (keyToNode.containsKey(key)) {
      keyToNode.get(key).value = value;
      get(key);
      return;
    }

    if (cache.size() == capacity) {
      Node lastNode = cache.iterator().next();
      cache.remove(lastNode);
      keyToNode.remove(lastNode.key);
    }

    Node node = new Node(key, value);
    cache.add(node);
    keyToNode.put(key, node);
  }

  private int capacity;
  private Set<Node> cache = new LinkedHashSet<>();
  private Map<Integer, Node> keyToNode = new HashMap<>();
}

class Node:
  def __init__(self, key: int, value: int):
    self.key = key
    self.value = value
    self.prev = None
    self.next = None


class LRUCache:
  def __init__(self, capacity: int):
    self.capacity = capacity
    self.keyToNode = {}
    self.head = Node(-1, -1)
    self.tail = Node(-1, -1)
    self.join(self.head, self.tail)

  def get(self, key: int) -> int:
    if key not in self.keyToNode:
      return -1

    node = self.keyToNode[key]
    self.remove(node)
    self.moveToHead(node)
    return node.value

  def put(self, key: int, value: int) -> None:
    if key in self.keyToNode:
      node = self.keyToNode[key]
      node.value = value
      self.remove(node)
      self.moveToHead(node)
      return

    if len(self.keyToNode) == self.capacity:
      lastNode = self.tail.prev
      del self.keyToNode[lastNode.key]
      self.remove(lastNode)

    self.moveToHead(Node(key, value))
    self.keyToNode[key] = self.head.next

  def join(self, node1: Node, node2: Node):
    node1.next = node2
    node2.prev = node1

  def moveToHead(self, node: Node):
    self.join(node, self.head.next)
    self.join(self.head, node)

  def remove(self, node: Node):
    self.join(node.prev, node.next)

Approach 2: std::list but TLE'd

• Time: get(key: int),, put(key: int, value: int): $O(1)$
• Space: $O(\texttt{capacity})$

C++

struct Node {
  int key;
  int value;
};

class LRUCache {
 public:
  LRUCache(int capacity) : capacity(capacity) {}

  int get(int key) {
    const auto it = keyToIterator.find(key);
    if (it == keyToIterator.cend())
      return -1;

    const auto& listIt = it->second;
    // Move it to the front.
    cache.splice(cache.begin(), cache, listIt);
    return listIt->value;
  }

  void put(int key, int value) {
    // There's no capacity issue, so just update the value.
    if (const auto it = keyToIterator.find(key); it != keyToIterator.cend()) {
      const auto& listIt = it->second;
      // Move it to the front.
      cache.splice(cache.begin(), cache, listIt);
      listIt->value = value;
      return;
    }

    // Check the capacity.
    if (cache.size() == capacity) {
      const Node& lastNode = cache.back();
      // That's why we store `key` in `Node`.
      keyToIterator.erase(lastNode.key);
      cache.pop_back();
    }

    cache.emplace_front(key, value);
    keyToIterator[key] = cache.begin();
  }

 private:
  const int capacity;
  list<Node> cache;
  unordered_map<int, list<Node>::iterator> keyToIterator;
};