Find top k frequent elements in an array of integers. Let’s first understand the problem statement and the we will solve this problem using multiple approaches.
Given a non-empty array of integers, return the k most frequent elements.
Example 1:
Input: arr = {3, 4, 4, 4, 7, 7}, k = 2
Output: {4, 7}
Two most frequent elements are 4 and 7.
Example 2:
Input: arr = {3}, k = 1
Output: {3}
NOTE:
* k is always valid, 1 ≤ k ≤ number of unique elements.
* The time complexity must be better than O(nlogn), where n is the array’s size.
* It’s guaranteed that the answer is unique, in other words, the set of the top k frequent elements is unique.
* Answer can be returned in any order.
Top K Frequent Elements
We have discussed the problem statement. How do we approach this problem? In this tutorial, I am going to explain three approaches and it’s java code to solve this problem.
Top K Frequent Elements Video Tutorial
Sort an array of 0s, 1s and 2s
Find first and last position of a number in a sorted array
Find Top K Most Frequent Numbers by using HashMap – Java Code
The idea here is to first traverse an array and create a map of all numbers and their count. The ideal data structure for storing key and value pairs is HashMap. The next step is to sort the HashMap by its value and pick only k elements.
The time complexity of this approach is O(nlogn) and its space complexity is O(n).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
//K Most Frequent Elements by sorting HashMap public static int[] topKFrequent(int[] nums, int k) { Map<Integer, Integer> elemCountMap = new HashMap<>(); for(int num : nums) { elemCountMap.put(num, elemCountMap.getOrDefault(num, 0)+1); } //Sort by values and pick only top k elements List<Integer> result = elemCountMap.entrySet().stream() .sorted((c1, c2) -> c2.getValue().compareTo(c1.getValue())) .limit(k) .map(i -> i.getKey()) .collect(Collectors.toList()); int[] resultArr = new int[result.size()]; for(int i = 0; i < result.size(); i++) { resultArr[i] = result.get(i); } return resultArr; } |
Find Top K Frequent Elements Solution using Priority Queue
Let’s improve our previous solution using a priority queue. To solve this problem first create a map of each element and its count. Then use a priority queue (Min Heap) and we keep its size equal to k.
Take all the keys of a map and put them in a Priority Queue. If the size of a priority queue is greater than k, In that case, we poll the top element which is the minimum element. Once all the elements of HashMap are put in a Priority queue, we only get the top k elements.
The time complexity of this approach is O(nlogk) and its space complexity is O(n).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
//Top K Frequent Elements LeetCode Solution using Priority Queue public static int[] topKFrequentPQ(int[] nums, int k) { Map<Integer, Integer> elemCountMap = new HashMap<>(); for(int num : nums) { elemCountMap.put(num, elemCountMap.getOrDefault(num, 0) + 1); } //Create a priority queue (Min heap) PriorityQueue<Integer> pq = new PriorityQueue<Integer>((num1, num2) -> elemCountMap.get(num1) - elemCountMap.get(num2)); for(int num : elemCountMap.keySet()) { pq.add(num); if (pq.size() > k) pq.poll(); } int[] resultArr = new int[k]; for(int i = k - 1; i >= 0; --i) resultArr[i] = pq.poll(); return resultArr; } |
Find Top K Frequent Elements – Java Code
In this example, Let’s discuss how we can solve this problem using bucket sort, and then we will write its java code.
Here are the following steps to solve this problem.
i) To find the most frequent elements, First, we need to know the number and its count. For this, we can use HashMap to store the number and its count.
So, if the input array is {1, 1, 1, 2, 2, 3, 3, 3} then at the end of this operation map would look like this: 1 -> 3, 2 -> 2, 3 -> 3.
We also need to keep track of maximum frequency, so its value, in this case, would be 3.
Sorting algorithms and their time complexities
ii) Then in the next step, create a list. At each index, we can store multiple elements. Its size would be maximum frequency + 1.
iii) Based on the frequency of a number put the number in the appropriate bucket. There might be more than one number with the same frequency, so we have to put them in the same bucket.
iv) Now, iterate over the bucket elements and print the k most frequent elements.
The time complexity of this approach is O(n).
I have also explained this approach using a video tutorial. The link to that video tutorial is present at the end of this post.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
/* Find Top K Most Frequent Numbers in an Array */ public class MostFrequentElements { public static int[] kMostFrequent(int[] nums, int k) { //Map which stores number and it's occurrence count Map<Integer, Integer> countMap = new HashMap<>(); //Variable which stores maximum frequency of any number int maxFreq = 0; //Traverse an array for(int i = 0; i < nums.length; i++) { //Get the occurrence of current element and add 1 int freq = countMap.getOrDefault(nums[i],0)+1; //put the elem and it's freq in a map countMap.put(nums[i], freq); //keep track of maximum occurrence maxFreq = Math.max(maxFreq, freq); } //Declare a bucket, which store multiple values List<Integer>[] bucket = new ArrayList[maxFreq + 1]; for(int n : countMap.keySet()) { int freq = countMap.get(n); if(bucket[freq]==null) bucket[freq] = new ArrayList<>(); bucket[freq].add(n); } int[] resultArr = new int[k]; int count = 0; //Pick top k elements for(int i = bucket.length-1; i >= 0; i--) { if(bucket[i]!=null){ for (int n : bucket[i]) { resultArr[count++] = n; if (count == k) return resultArr; } } } return resultArr; } public static void main(String[] args) { int[] arr = {3, 4, 4, 4, 7, 7}; int[] result = kMostFrequent(arr, 2); for(int elem : result) { System.out.print(elem + " "); } } } |
In this video tutorial, I have explained how we can solve this problem efficiently using map data structure and bucket sort.
