hi, let Avik connect you.


** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.

** You can check all the posts on the Posts page.

** More about me in the About Me section.

LFU Cache

  • Problem : 460. LFU Cache

  • Problem Link : leetcode.com/problems/lfu-cache/

  • Companies Asked : Apple, Amazon, Google, VMware, Oracle, Snapchat, LinkedIn, Microsoft, Walmart Global Tech


  • Approach:

    1. If you are struggling to solve this problem. Please go through this video by Striver https://www.youtube.com/watch?v=0PSB9y8ehbk.

    2. Declare three hashmaps, frequencyList, keyNode, and frequency.

    3. The key of frequencyList is an integer. And the value will be a list. The frequencyList contains elements of a certain frequency.

    4. The key of keyNode is an integer and the corresponding value is an iterator containing the iterator for an element of a specific frequency of frequencyList.

    5. The key of frequency is an integer and the corresponding value is a pair of two other integers containing the frequency count and the value of a particular key.

    6. Two more variables minFrequency holds the minimum frequency from which we need to remove the number if we are at capacity and currentSize determining the size of the LFUCache.

    7. For the put() function -

      • If the capacity is less than 1, no put() operation will take place.

      • Now, if the given key is a new one and we are at capacity then we need to remove the least used key.

      • We will remove the very last element available from the frequencyList of minFrequency index. We also remove that element from frequency hashmap as well.

      • As the item is a new one then, the minFrequency will be set to 1. And we will add them in frequencyList's minFrequency index, frequency, and keyNode.

      • If the key is not new, then we need to add the value to the frequency hashmap.

      • Then we will call the get() function.

    8. Now for the get() function -

      • If the key is new then we need to return -1.

      • If the key is not new, then we need to erase that key from the frequencyList.

      • Also, increase the frequency count of the current element.

      • Insert them into the frequencyList.

      • If the minFrequency list is 0, then increase minFrequency by 1.

      • Return the corresponding value for the given key.


  • Time and Space Complexity:

      • Time Complexity: O(1)

      • Space Complexity: O(1)


Code [C++]

class LFUCache {

public:

int Capacity, minFrequency = 0, currentSize = 0;

unordered_map<int, list<int>>frequencyList;

unordered_map<int, list<int>::iterator>keyNode;

unordered_map<int, pair<int, int>>frequency;


LFUCache(int capacity) {

Capacity = capacity;

minFrequency = 0, currentSize = 0;

}

int get(int key) {

if(keyNode.find(key) == keyNode.end()) return -1;

int keyFreq = frequency[key].first;

frequencyList[keyFreq].erase(keyNode[key]);

frequency[key].first++;

frequencyList[frequency[key].first].push_front(key);

keyNode[key] = frequencyList[frequency[key].first].begin();

if(frequencyList[minFrequency].size() == 0) minFrequency++;

return frequency[key].second;

}

void put(int key, int value) {

if(Capacity <= 0) return;

if(keyNode.find(key) != keyNode.end()){

frequency[key].second = value;

get(key);

return;

}

// New Element

if(currentSize == Capacity){

int minFreqBack = frequencyList[minFrequency].back();

keyNode.erase(minFreqBack);

frequency.erase(key);

frequencyList[minFrequency].pop_back();

currentSize--;

}

currentSize++;

minFrequency = 1;

frequencyList[minFrequency].push_front(key);

keyNode[key] = frequencyList[minFrequency].begin();

frequency[key].first = 1, frequency[key].second = value;

}

};


/**

* 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);

*/