
This video explains a very important programming interview problem which is to find the top k frequent elements in a given array.This problem is based on heap and hashmap.I have shown all the required concepts by showing the intuition using examples.I have first explained the simple solution and then optimized to give a better solution.I have explained the problem in two different ways using heap and hash and i have also compared the efficiency with each other and showed which is better and why.
Top K Frequent Elements
class Solution { struct node{ int no; int freq; node(int a,int b) //Constructor for value initialization for each node { no = a; freq = b; } }; struct compare { //Maintains MAX-HEAP based on frequency bool operator()(node const& a, node const& b) { return a.freq < b.freq; } }; public: vector<int> topKFrequent(vector<int>& nums, int k) { unordered_map<int,int> m; //Key->Number...Value->Freq //STEP-1: Store frequency of all elements in map for(int ele: nums) m[ele]+=1; //STEP-2: Now build a heap priority_queue<node,vector<node>,compare> heap; //Compare defines a max-heap based on frequency for(auto it: m) heap.push(node(it.first,it.second)); vector<int> ans; //Stores top-K elements //STEP-3: Pop top-k elemnts and store the numbers in ans vector while(k--) { node temp = heap.top(); heap.pop(); ans.push_back(temp.no); } return ans; } };