LFU Cache

class LFUCache {
public:
    unordered_map<int, int> freq; // key, kitne baar used
    unordered_map<int, list<int>> freqKeys;
    
    // 2 -> {_ _} // lru
    // 3 -> {_ _ [] _ [3]}
    // 4 -> {}


    unordered_map<int, pair<int, list<int>::iterator>> mp; // p.first = key
                                                           // p.second = {value, iterator}
    int lfu; // least frequenty used ka frequency
    int capacity;
    LFUCache(int capacity) {
        this->capacity = capacity;
        lfu = 0;
    }

    void touch(int key) {
        int count = freq[key];
        freq[key]++;
        auto p = mp[key].second;
        freqKeys[count].erase(p);
        freqKeys[freq[key]].push_back(key);

        if(freqKeys[lfu].size() == 0) {
            lfu++;
        }
        mp[key].second = --(freqKeys[freq[key]].end());

    }
    
    int get(int key) {
        if (mp.find(key) == mp.end()) {
            return -1;
        }
        touch(key);
        return mp[key].first;
        
    }
    
    void put(int key, int value) {
        if(mp.find(key) != mp.end()) {
            mp[key].first = value;
            touch(key);
            return;
        }

        if(mp.size() == capacity) {
            int keyToRemove = *freqKeys[lfu].begin();
            freq.erase(keyToRemove);
            auto p = mp[keyToRemove].second;
            freqKeys[lfu].erase(p);
            mp.erase(keyToRemove);
        }
        lfu = 1;
        freq[key] = lfu;
        freqKeys[lfu].push_back(key);
        mp[key] = {value, --freqKeys[lfu].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);
 */