K Most Frequent Elements

Prerequisite: Quick Sort

In this approach, we will try to divide the problem at every step into a smaller problem. We know that the kth top frequent element is (n - k)th less frequent. So, we will do a partial sort from the less frequent element to the most frequent one, till (n - k)th less frequent element takes place (n - k) in a sorted array. To do so, we will use quickselect. Quickselect is an algorithm used to find the kth smallest element in an array. In this problem, we will modify the general quickselect algorithm to find (n - k)th less frequent element. 

We will perform quickselect on an array containing all the keys of the hash map where the key is an element of ‘ARR’ and value is how often this element appears in 'ARR'. We will use a partition scheme to put all the less frequent elements to the left of the pivot and the more frequent elements to the right of the pivot. Then, we will put the pivot element at its correct position in the final sorted array(sorted according to the frequencies). When the pivot reaches the target position, i.e.,(n - k)th position, then all the elements to its right will be k most frequent elements.

Algorithm :

• Initialize a hash map ‘MAP’ where the key is the element and value is how often this element appears in ‘ARR’.
• Iterate every element in ‘ARR’:
  • Add the current element to ‘MAP’ and increase its value by 1.
• Set ‘SIZE’ as ‘MAP.SIZE’.
• Initialize an integer array ‘UNIQUE’ and add all the keys of ‘MAP’ to it.
• Call ‘QUICKSELECT’(0, ‘SIZE’ - 1, ‘SIZE’ -’K’).
• Return elements of ‘UNIQUE’ from index‘(SIZE’ - ’K’) to ‘SIZE’.

Maintain a function ‘QUICKSELECT’(‘LEFT’, ‘RIGHT’, ‘KSMALL’):

• If ‘LEFT’ is equal to ‘RIGHT’, return.
• Select a random pivot between ‘LEFT’ to ‘RIGHT’.
• Set ‘PIVOT’ as ‘PARTITION’(‘LEFT’, ‘RIGHT’, ‘PIVOT’).
• If ‘KSMALL’ is equal to ‘PIVOT’, return.
• Otherwise, if ‘KSMALL’ is less than ‘PIVOT’, call quickselect on the left partition.
• Otherwise, call quickselect on the right partition.

Maintain a function ‘PARTITION’(‘LEFT’, ‘RIGHT’, ‘PIVOT’):

• Set ‘PIVOTFREQUENCY’ as the frequency of ‘UNIQUE’[‘PIVOT’].
• Swap ‘UNIQUE’[‘PIVOT’] and ‘UNIQUE’[‘RIGHT’].
• Set ‘IDX’ as ‘LEFT’.
• Iterate ‘I’ in ‘LEFT’ to ‘RIGHT’
  • If the frequency of ‘UNIQUE’[‘I’] is less than the frequency of the pivot element, move ‘UNIQUE’[‘I’] to the left of the pivot element and increment ‘IDX’ by 1.
• Swap ‘UNIQUE’[‘IDX’] and ‘UNIQUE’[‘RIGHT’].
• Return ‘IDX’.

In this approach, we will sort the unique elements of the input array according to how often this element appears in 'ARR'. We will use a hasp map where the key is element and value is how often this element appears in 'ARR'. Then we will initialize a heap where elements will be sorted in descending order according to the element’s frequency. We will add all the keys of the hash map to the heap and return the first ‘K’ elements of the heap.

Algorithm :

• If ‘K’ is equal to ‘N’, return ‘ARR’.
• Initialize a hash map ‘MAP’ where the key is the element and value is how often this element appears in ‘ARR’.
• Iterate every element in ‘ARR’:
  • Add the current element to ‘MAP’ and increase its value by 1.
• Initialize a priority queue ‘HEAP’ where elements will be sorted in descending order according to the element’s frequency.
• Add all the keys of ‘MAP’ in ‘HEAP’.
• Initialize an array ‘ANS’.
• Add first ‘K’ elements of ‘HEAP’ to ‘ANS’.
• Return ‘ANS’.

95We can observe that frequency of any element in ‘ARR’ can be a minimum of one and maximum ‘N’. So, we can create N buckets and add each unique element in the respective bucket according to its frequency. For example, for any element having frequency X we go to BUCKET[X]. After adding all the unique elements in their respective buckets, the ‘K’ elements starting from the rightmost buckets will be our answer.

Algorithm :

• Initialize a hash map ‘MAP’ where the key is the element and value is how often this element appears in ‘ARR’.
• Iterate every element in ‘ARR’:
  • Add the current element to ‘MAP’ and increase its value by 1.
• Initialize an array of lists‘ BUCKETS’.
• Add all the keys of the hash map in the respective according to their frequency.
• Add 'K' elements to answer array ‘ANS’ starting from the rightmost bucket.
• Return ‘ANS’.