Daily Coding-Day 2
LC Problem #347 - The Quickselect Algorithm
Today I learnt the famous Top K Frequent Elements problem. A couple of years back this problem was all the rage in major FAANG interviews. However, recently its stock seems to have dropped quite a bit. Nonetheless, this is a good problem to demonstrate the utility of Hoare's Quickselect Algorithm.
Hoare's Quickselect Algorithm
The Quickselect Algorithm is a practically used algorithm, to find answers to questions like "K Most Frequent", "K Least Frequent", "Kth Largest/Smallest" and so on. It promises an average time complexity of O(n) and a worst case time complexity of O(n^2). However, when the pivot for the partitioning is selected in a random manner, the probability of worst case happening is negligible and hence, the Algorithm performs pretty well.
The Pre-requisites:
- To find K most frequent elements we need, yeah you guessed it right - frequencies of each element which can be stored in a Hashtable or a Hashmap. Lets call the same count
for(int num: nums){
count.put(num, count.getOrDefault(num, 0)+1);
}
- The second Collection we would need is an array of all the unique elements given in the original array, which we are going to sort in increasing order of their frequencies, using the quicksort technique.
for(int num: count.keySet()){
unique[i++] = num;
}
The Algorithm:
- Having done all the precomputations required for the algorithm, its time to put the quickselect into action. We do that by calling the quickselect function with initial start and end values of 0 and n-1 respectively, and we are looking for n-kth least frequent index.
- The Partition Algorithm : There are a plethora of partitioning algorithms available on the internet, I prefer going with a simple one like Lomuto's Partitioning
- Beauty of Quickselect: We can close down our answer space depending on the pivot index returned by the partitioning algorithm.
pivot_index = left + random.nextInt(right-left);
pivot_index = partition(left, right, pivot_index);
if(pivot_index == k_frequent)
return pivot_index;
else if(pivot_index > k_frequent)
return quickselect(left, pivot_index-1, k_frequent);
else
return quickselect(pivot_index+1, right, k_frequent);
The Entire Code can be found here:
https://github.com/popty/LeetCodes/tree/main/347-top-k-frequent-elements