LFU Cache — Least Frequently Used

class LFU {
  Map keyMap;      // key → node
  Map> freqMap;  // freq → ordered list of nodes
  int minFreq;
  int capacity;
}
class Node { int key, val, freq; }

public int get(int key) {
  Node n = keyMap.get(key);
  if (n == null) return -1;
  // Remove from current freq list, add to next
  freqMap.get(n.freq).remove(n);
  if (freqMap.get(minFreq).isEmpty() && n.freq == minFreq) minFreq++;
  n.freq++;
  freqMap.computeIfAbsent(n.freq, k -> new LinkedList<>()).addFirst(n);
  return n.val;
}