460. LFU Cache

• Time: $O(1)$
• Space: $O(n)$

C++JavaPython

struct Node {
  int key;
  int value;
  int freq;
  list<int>::const_iterator it;
};

class LFUCache {
 public:
  LFUCache(int capacity) : capacity(capacity), minFreq(0) {}

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

    Node& node = it->second;
    touch(node);
    return node.value;
  }

  void put(int key, int value) {
    if (capacity == 0)
      return;
    if (const auto it = keyToNode.find(key); it != keyToNode.cend()) {
      Node& node = it->second;
      node.value = value;
      touch(node);
      return;
    }

    if (keyToNode.size() == capacity) {
      // Evict an LRU key from `minFreq` list.
      const int keyToEvict = freqToList[minFreq].back();
      freqToList[minFreq].pop_back();
      keyToNode.erase(keyToEvict);
    }

    minFreq = 1;
    freqToList[1].push_front(key);
    keyToNode[key] = {key, value, 1, freqToList[1].cbegin()};
  }

 private:
  int capacity;
  int minFreq;
  unordered_map<int, Node> keyToNode;
  unordered_map<int, list<int>> freqToList;

  void touch(Node& node) {
    // Update the node's frequency.
    const int prevFreq = node.freq;
    const int newFreq = ++node.freq;

    // Remove the iterator from `prevFreq`'s list
    freqToList[prevFreq].erase(node.it);
    if (freqToList[prevFreq].empty()) {
      freqToList.erase(prevFreq);
      // Update `minFreq` if needed.
      if (prevFreq == minFreq)
        ++minFreq;
    }

    // Insert the key to the front of `newFreq`'s list.
    freqToList[newFreq].push_front(node.key);
    node.it = freqToList[newFreq].cbegin();
  }
};

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

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

    final int freq = keyToFreq.get(key);
    freqToLRUKeys.get(freq).remove(key);
    if (freq == minFreq && freqToLRUKeys.get(freq).isEmpty()) {
      freqToLRUKeys.remove(freq);
      ++minFreq;
    }

    // Increase key's freq by 1
    // Add this key to next freq's list
    putFreq(key, freq + 1);
    return keyToVal.get(key);
  }

  public void put(int key, int value) {
    if (capacity == 0)
      return;
    if (keyToVal.containsKey(key)) {
      keyToVal.put(key, value);
      get(key); // Update key's count
      return;
    }

    if (keyToVal.size() == capacity) {
      // Evict an LRU key from `minFreq` list.
      final int keyToEvict = freqToLRUKeys.get(minFreq).iterator().next();
      freqToLRUKeys.get(minFreq).remove(keyToEvict);
      keyToVal.remove(keyToEvict);
    }

    minFreq = 1;
    putFreq(key, minFreq);    // Add new key and freq
    keyToVal.put(key, value); // Add new key and value
  }

  private int capacity;
  private int minFreq = 0;
  private Map<Integer, Integer> keyToVal = new HashMap<>();
  private Map<Integer, Integer> keyToFreq = new HashMap<>();
  private Map<Integer, LinkedHashSet<Integer>> freqToLRUKeys = new HashMap<>();

  private void putFreq(int key, int freq) {
    keyToFreq.put(key, freq);
    freqToLRUKeys.putIfAbsent(freq, new LinkedHashSet<>());
    freqToLRUKeys.get(freq).add(key);
  }
}

class Node:
  def __init__(self, key: int, value: int, freq: int, it):
    self.key = key
    self.value = value
    self.freq = freq
    self.it = it


class LFUCache:
  def __init__(self, capacity: int):
    self.capacity = capacity
    self.minFreq = 0
    self.keyToNode = {}
    self.freqToList = {}

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

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

  def put(self, key: int, value: int) -> None:
    if self.capacity == 0:
      return

    if key in self.keyToNode:
      node = self.keyToNode[key]
      node.value = value
      self._touch(node)
      return

    if len(self.keyToNode) == self.capacity:
      # Evict an LRU key from `minFreq` list
      keyToEvict = self.freqToList[self.minFreq][-1]
      self.freqToList[self.minFreq].pop()
      del self.keyToNode[keyToEvict]

    self.minFreq = 1
    if 1 not in self.freqToList:
      self.freqToList[1] = []
    self.freqToList[1].insert(0, key)
    self.keyToNode[key] = Node(key, value, 1, 0)  # Using index 0 as iterator

  def _touch(self, node: Node) -> None:
    # Update the node's frequency
    prevFreq = node.freq
    node.freq += 1
    newFreq = node.freq

    # Remove the key from `prevFreq`'s list
    self.freqToList[prevFreq].remove(node.key)
    if not self.freqToList[prevFreq]:
      del self.freqToList[prevFreq]
      # Update `minFreq` if needed
      if prevFreq == self.minFreq:
        self.minFreq += 1

    # Insert the key to the front of `newFreq`'s list
    if newFreq not in self.freqToList:
      self.freqToList[newFreq] = []
    self.freqToList[newFreq].insert(0, node.key)
    node.it = 0  # Using index 0 as iterator