# C++ O(1) solution using Hash Table and List

• ``````class LFUCache {
map<int, list<pair<int,int>>> arr;   //Index: frequency, value:  store key and value pairs
unordered_map<int, pair<int, list<pair<int,int>>::iterator> > hash; // stores frq and (key, value) for O(1)
int cap ;
int cnt ;
public:
LFUCache(int capacity) {
cap = capacity;
cnt = 0;
}

int get(int key) {
if(hash.count(key) == 0) return -1;
auto it = hash[key];
auto pos = it.second;
int val = pos->second;
int frq = it.first;

arr[frq].erase(pos);
if(arr[frq].size() == 0) {
arr.erase(arr.find(frq));
}

arr[frq+1].push_back(make_pair(key,val));
pos = arr[frq+1].end();
pos--;
hash[key].second = pos;
hash[key].first++;

return val;
}

void set(int key, int value) {
if(cap == 0) return ;
if(hash.count(key) > 0){
get(key);
hash[key].second->second = value;
}else{
if(cnt == cap){
auto st = arr.begin();
int toRemove = st->second.begin()->first;
hash.erase(toRemove);
st->second.pop_front();
if(st->second.size() == 0){
arr.erase(st);
}
}else{
cnt++;
}

arr[1].push_back(make_pair(key,value));
auto it = arr[1].end();
it--;
hash[key].second = it;
hash[key].first = 1;
}
}
};
``````

• Find of Map has complexity of logarithmic in the size of the container.

• This post is deleted!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.