K Most Frequent Elements

Moderate
0/80
Average time to solve is 10m
profile
Contributed by
48 upvotes
Asked in companies
WalmartOracleFacebook

Problem statement

You are given an Integer array ‘ARR’ and an Integer ‘K’.


Your task is to find the ‘K’ most frequent elements in ‘ARR’. Return the elements in any order.


For Example:

You are given ‘ARR’ = {1, 2, 2, 3, 3} and ‘K’ = 2. 

The answer will {2, 3} as 2 and 3 are the elements occurring most times.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains two space-separated integers, ‘N’ and ‘K’, representing the size of ‘ARR’ and the given integer ‘K’, respectively.

The second line contains ‘N’ space-separated integers representing the elements of ‘ARR’.
Output Format: 
The only line contains the ‘K’ most frequent elements in ‘ARR’.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Sample Input 1:
5 2
1 2 2 3 3
Sample Output 1:
2 3
Explanation of Sample Input 1:
The answer will {2, 3} as 2 and 3 are the elements occurring the most number of times.
Sample Input 2:
2 2
1 2
Sample Output 2:
1 2
Constraints:
1 <= 'N' <= 10^5
1 <= 'K' <= Number of unique elements in ‘ARR’
1 <= 'ARR[i]' <= 10^6

Time Limit: 1 sec
Hint

Divide and conquer.

Approaches (3)
QuickSelect

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’.
Time Complexity

O(N ^ 2), where 'N' is the size of the input array.

 

The worst-case time complexity of quickselect is O(N ^ 2) when bad pivots are which doesn’t divide the problem in half are chosen constantly. But when the pivots are chosen randomly, the probability of such a worst-case is small. The average case time complexity of quickselect is O(N).

Space Complexity

O(N).

 

The Hash map and the array of unique elements can have at most N elements. Hence, the total space complexity is O(N).

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
K Most Frequent Elements
Full screen
Console