# Leetcode 460 Solution

https://leetcode.com/problems/lfu-cache

## Solution

``````class LFUCache {
unordered_map<int, tuple<int, int, list<int>::iterator>> m;
map<int, list<int>> freqs;

int m_cap;
public:
list<int>::iterator insertFreq(int freq, int key) {
freqs[freq].push_back(key);
return --freqs[freq].end();
}

void eraseFreq(int freq, const list<int>::iterator& it) {
freqs[freq].erase(it);
if (freqs[freq].empty())
freqs.erase(freq);
}

LFUCache(int capacity) {
m_cap = capacity;
}

int get(int key) {
auto it = m.find(key);

if (it == m.end())
return -1;

int& val = std::get<0>(it->second);
int& freq = std::get<1>(it->second);
auto& list_it = std::get<2>(it->second);

eraseFreq(freq, list_it);

freq += 1;

list_it = insertFreq(freq, key);

return val;
}

void put(int key, int value) {
if (m_cap == 0)
return;

int old_value = get(key);

if (old_value != -1)
{
auto it = m.find(key);
std::get<0>(it->second) = value;
return;
}

if (m.size() == m_cap)
{
int freq_to_remove = freqs.begin()->first;
int key_to_remove = freqs.begin()->second.front();
eraseFreq(freq_to_remove, freqs.begin()->second.begin());

m.erase(key_to_remove);
}

freqs[1].push_back(key);
m[key] = make_tuple(value, 1, --freqs[1].end());
}
};

/**
* Your LFUCache object will be instantiated and called as such:
* LFUCache* obj = new LFUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/
``````