Given a non-empty array of integers arr , write a program to return the k most frequent elements in the form of an array.

Problem Note

  • You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
  • Your algorithm's time complexity must be better than O(n log n) , where n is the array's size.
  • The elements of the resultant array may be in any order.

Example 1 

Input: arr[] = [3, 0, 1, 0], k = 1
Output: [0]
Explanation: 0 is the top-most frequent element having frequency of 2.

Example 2 

Input: arr[] = [1, 2], k = 2
Output: [1, 2]
Explanation: 1 and 2 are the top 2 frequent elements having frequency of 1.