Given an integer array nums and an integer k, return the k most
frequent elements. You may return the answer in any order.
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Explanation: '1' appeared three times and '2' appeared two times, they are the top 2 frequent elements.
Input: nums = [1], k = 1
Output: [1]
Follow up:
Your algorithm's time complexity must be better than O(n log n), where n is the array's size. (Solution 3 and 4 below runs with O(n) time complexity)
Contents
- Solution 1 - using sorting, find number of times each element appeared and then sort them by that count
- Solution 2 - using Min Heap, find number of times each element appeared and then add to min heap with at most 'k' elements
- Solution 3 - using QuickSelect algorithm
- Solution 4 - using a technique used in BucketSort (easy and most efficient solution)
In this approach, we are going to loop through numbers in nums array and store the number as key to its count of how many
times that number have appeared as value into a HashMap.
Then, copy the entries of HashMap into a List and sort them by the count of how many times that it appeared. i.e. using entry's value.
(The reason we are copying into a List is because, we want to use Java's inbuilt sorting utility functions).
After the entries are sorted, take the last k elements from sorted list.
Consider an example with nums[1, 1, 1, 2, 3, 2, 1] and k = 2, so we need to find top 2 frequent elements.
-
In the first step, we will initialize a HashMap and store the count of each number to number of times it appeared.
HashMap<Integer, Integer> map = new HashMap<>();
IntStream.of(nums).forEach(num->map.merge(num, 1, Integer::sum));
Now, the HashMap will looks like this. 1 appeared 4 times, 2 appeared 2 times and
3 appeared 1 time.
Mapping
| key |
value |
| 1 |
4 |
| 2 |
2 |
| 3 |
1 |
-
Now, take these entries into a ArrayList and sort them by count of the number.
ArrayList<Map.Entry<Integer, Integer>> list = new ArrayList<>(map.entrySet());
list.sort(Comparator.comparingInt(Map.Entry::getValue));
After sorting, it looks like this.
List after sorting
| entry key |
entry value |
| 3 |
1 |
| 2 |
2 |
| 1 |
4 |
-
Now, we will return the last two eleemnts from this sorted list. i.e. [2, 1] or [1, 2] in any order.
import java.util.*;
import java.util.function.Function;
import java.util.stream.IntStream;
public class TopKFrequentElements {
/**
* First, store the mapping of number -> number of times it appeared into a HashMap
* Second, sort the entries of HashMap using the values (number of times a number is appeared)
* Then, take last K elements
*/
static int[] usingSorting(int[] nums, int k) {
int[] ans = new int[k];
HashMap<Integer, Integer> map = new HashMap<>();
IntStream.of(nums).forEach(num->map.merge(num, 1, Integer::sum));
ArrayList<Map.Entry<Integer, Integer>> list = new ArrayList<>(map.entrySet());
list.sort(Comparator.comparingInt(Map.Entry::getValue));
for(int i=0; i<k; i++) {
ans[i] = list.get(list.size()-1-i).getKey();
}
return ans;
}
}
Complexity Analysis:
Time complexity: Above code runs in O(n log(n)) time where n is the input array nums length.
Space complexity: O(n).
In this approach, we are going to loop through numbers in nums array and store the number as key to its count of how many
times that number appeared as value into a HashMap.
In the next step we are going to create a PriorityQueue (Heap data structure in Java with default implementation of min heap,
meaning that parent node will always have min value than its children).
Then in the next step, we will loop through HashMap entries and then add to the PriorityQueue,
while doing that keep checking if PriorityQueue size is exceeding size k, whenever it exceeds size k remove elements from PriorityQueue
so that it only keeps top k elements only.
Finally return the elements from the PriorityQueue.
Consider an example with nums[1, 1, 1, 2, 3, 2, 1] and k = 2, so we need to find top 2 frequent elements.
-
In the first step, we will initialize a HashMap and store the count of each number to number of times it appeared.
HashMap<Integer, Integer> map = new HashMap<>();
IntStream.of(nums).forEach(num->map.merge(num, 1, Integer::sum));
Now, the HashMap will looks like this. 1 appeared 4 times, 2 appeared 2 times and
3 appeared 1 time.
Mapping
| key |
value |
| 1 |
4 |
| 2 |
2 |
| 3 |
1 |
-
Now we will initialize PriorityQueue which will use HashMap entry's value when it needs to orders elements inside Heap.
PriorityQueue<Map.Entry<Integer, Integer>> minHeap = new PriorityQueue<>(k, Comparator.comparingInt(Map.Entry::getValue));
-
Now, then loop through HashMap entries, add them to the PriorityQueue we created above and whenever it reaches k+1 size
then remove the top element, so that it keeps only k elements.
map.entrySet().forEach(entry->{
minHeap.offer(entry);
if(minHeap.size() >k) {
minHeap.poll();
}
});
At the end PriorityQueue, it looks like this.
List after sorting
| entry key |
entry value |
| 1 |
4 |
| 2 |
2 |
-
Now, we will return the eleemnts from this PriorityQueue, which will be [1, 2]
import java.util.*;
import java.util.function.Function;
import java.util.stream.IntStream;
public class TopKFrequentElements {
/**
*
* First, store the mapping of number -> number of times it appeared into a HashMap
* Next, Crate a Min Heap (default Java Priority Queue is Min heap, i.e. at top it keeps min element and children are greater than parent)
* Then, loop through entries of HashMap and add it to PriorityQueue, if it is reaches size 'k' then poll, by the end will have top k elements
*/
static int[] usingHeap(int[] nums, int k) {
HashMap<Integer, Integer> map = new HashMap<>();
IntStream.of(nums).forEach(num->map.merge(num, 1, Integer::sum));
final PriorityQueue<Map.Entry<Integer, Integer>> minHeap = new PriorityQueue<>(k, Comparator.comparingInt(Map.Entry::getValue));
map.entrySet().forEach(entry->{
minHeap.offer(entry);
if(minHeap.size() >k) {
minHeap.poll();
}
});
int[] result = new int[k];
for(int i=0;i<k; i++) {
result[i] = minHeap.poll().getKey();
}
return result;
}
}
Complexity Analysis:
Time complexity: Above code runs in O(n log(k)) time where n is the input array nums length and when PriorityQueue's
heapify() function takes log k, since there will be at most k elements in the heap.
Space complexity: O(n).
In this approach, we are apply Quickselect algorithm
(I have provided detailed explanation in Find Kth Largest Element problem's Solution 3).
We will be leveraging the same solution here. The main advantage with this solution is that, initially we will be selecting a random indexed element
from the input array and call it pivot, then just like in quick sort algorithm, we will then move all elements smaller to the pivot to the left side of the pivot
and all elements greater than pivot to the right side of the pivot, after this step pivot element is correctly positioned in the array if it is sorted.
Now we can draw a decision based on where pivot index is placed now:
-
If k and pivot element's index are same, that means we have found our answer. All elements on the right side of pivot element are the top K frequent elements.
-
If k is less than pivot element's index, that means we have left some elements on the left side of the array to cover top K frequent elements.
Now, we update our scope of algorithm to 0th index to pivot's index.
-
If k is greater than pivot element's index, that means we have extra elements on the right side of the array to cover top K frequent elements.
Now, we update our scope of algorithm to pivot's index right index.
If you observe in these steps, in each step we are reducing the scope of the algorithm to either left or right side of elements to the pivot without sorting them.
This algorithm runs with average time complexity of O(n) in average case, but worst case time complexity of O(n2).
import java.util.*;
import java.util.function.Function;
import java.util.stream.IntStream;
public class TopKFrequentElements {
/**
* Using QuickSelect algorithm
*/
static int[] usingQuickSelect(int[] nums, int k) {
HashMap<Integer, Integer> map = new HashMap<>();
IntStream.of(nums).forEach(num->map.merge(num, 1, Integer::sum));
Map.Entry<Integer, Integer>[] entries= map.entrySet().toArray(new Map.Entry[0]);
// we are passing k as entries.length - k, because we need last k elements
selectTopKFrequent(entries, 0, entries.length-1, entries.length-k); //entries wil be updated by reference
int[] result = new int[k];
for(int i=0; i<k; i++) { // take last k elements from array
result[i] = entries[entries.length-1-i].getKey();
}
return result;
}
static void selectTopKFrequent(Map.Entry<Integer, Integer>[] entries, int left, int right, int k) {
if(left == right) {
return;
}
int storeIndex = partition(entries, left, right);
if(storeIndex == k) {
//k is positioned at the right place
return;
} else if (k< storeIndex) { // if K is smaller than current pivot, move to the left
selectTopKFrequent(entries, left, storeIndex -1, k);
} else {
selectTopKFrequent(entries, storeIndex+1, right, k);
}
}
static int partition(Map.Entry<Integer, Integer>[] entries, int left, int right) {
Map.Entry<Integer, Integer> pivotIndexElement = entries[right]; //we are choosing right index to be pivot index, but we can select any random one
int storeIndex = left;
for(int i=left;i<right; i++) {
if(entries[i].getValue() < pivotIndexElement.getValue()) {
// swap these entries
swap(entries, i, storeIndex);
storeIndex++;
}
}
swap(entries, right, storeIndex); // move pivot to its final place, meaning that,
// left side elements are now smaller than pivot and right elements
// are greater than pivot
return storeIndex;
}
// utility to swap i, j indexed elements
static void swap(Map.Entry<Integer, Integer>[] entries, int i, int j) {
Map.Entry<Integer, Integer> temp = entries[i];
entries[i] = entries[j];
entries[j] = temp;
}
}
Complexity Analysis:
Time complexity: Above code runs in O(n) time in average case, but takes O(n2) in worst case where n is the input array nums length.
heapify() function takes log k, since there will be at most k elements in the heap.
Space complexity: O(n) for storing elements count into HashMap.
In this approach we will be using a technique from Bucket Sort, but we will not be sorting the array, so we will not be discussing details of bucket sorting here.
Similar to all above approaches, we will first go through array and count how many times an element appeared and store this information into a HashMap.
Next, we will create an array with the same size as input array, each element in the array will be a bucket (we will use an ArrayList).
Then, we will go through entries of HashMap and store elements into array buckets into the index whose value will be same as
the number of times it appeared. (No element in array will appear more than the times of input array length, this is the key to this solution).
For example, say nums = [1, 1, 1, 3, 2, 2, 4, 1] and k =2, in the input array 1 appeared 4 times,
2 appeared 2 times, 3 appeared 1 time and 4 appeared 1 time.
Now, when we place these into buckets array, this is how it will look like. (we have created n+1 buckets to map exactly n count to nth index).
buckets = [null, [3, 4], [2], null, [1], null, null, null, null]
1 appeared 4 times, so we have placed it in index 4, similarly we have placed 2, 3 and 4 into respective indices based on number of times they have appeared.
Now, we can loop this buckets array from right to left and just take k elements.
import java.util.*;
import java.util.function.Function;
import java.util.stream.IntStream;
public class TopKFrequentElements {
/**
*
* Using a temporary array to store elements into respective indexes based the number of times they have appeared.
*/
static int[] usingBucketSortingTechnique(int[] nums, int k) {
HashMap<Integer, Integer> map = new HashMap<>();
IntStream.of(nums).forEach(num->map.merge(num, 1, Integer::sum));
// Now, we will create n buckets to store count of number of times an element appeared
// index of array is the number of times an element appeared, within that bucket we will store elements
// that have appeared same number of times
List<Integer>[] buckets = new List[nums.length+1];// added +1 to keep n times appeared element into n(th) index
map.forEach((key, value) -> {
if (buckets[value] == null) {
buckets[value] = new ArrayList<>();
}
buckets[value].add(key);
});
int[] result = new int[k];
for(int i= buckets.length-1; i>=0 && k>0 ; i--) {
if(buckets[i] != null) {
List<Integer> elements = buckets[i];
for(int j=0; j<elements.size() && k>0; j++) {
result[k-1] = elements.get(j);
k--;
}
}
}
return result;
}
}
Complexity Analysis:
Time complexity: Above code runs in O(n) time where n is the input array nums length.
Space complexity: O(n) for storing elements count into HashMap.
Above implementations source code can be found at
GitHub link for Java code