---
title: leetcode 460
tags: leetcode, hashMap
---

// https://leetcode.com/problems/lfu-cache/
class LFUCache {
private:
  int capacity, size, minFreq;
  unordered_map<int, pair<int, int>> m; // key -> value, freq
  unordered_map<int, list<int>::iterator> key2Iter;
  unordered_map<int, list<int>> freq2List;

public:
  LFUCache(int capacity) : capacity(capacity) { size = 0; }

  int get(int key) {
    if (m.count(key) == 0)
      return -1;
    freq2List[m[key].second].erase(key2Iter[key]);
    m[key].second++;
    freq2List[m[key].second].push_back(key);
    key2Iter[key] = --freq2List[m[key].second].end();

    if (freq2List[minFreq].size() == 0)
      minFreq++;
    return m[key].first;
  }

  void put(int key, int value) {
    if (capacity == 0)
      return;
    int stored = get(key);
    if (stored != -1) {
      m[key].first = value;
      return;
    }

    if (size == capacity) {
      int toDelete = freq2List[minFreq].front();
      freq2List[minFreq].pop_front();
      m.erase(toDelete);
      key2Iter.erase(toDelete);
      size--;
    }

    m[key] = {value, 1};
    freq2List[1].push_back(key);
    key2Iter[key] = --freq2List[1].end();
    minFreq = 1;
    size++;
  }
};